Is a halfspace intersection unbounded?
Brad Barber
bradb at shore.net
Fri Dec 3 18:58:58 PST 2004
A Qhull user asked the following question:
Marcin Kuropatwinski:
I am interested if the qhalf can provide information if the given halfspace intersection is bounded (has finite volume) or unbouded (infinite volume). In the options I did not found any hint. Do you know some solution to this problem? The dimension of the problem is 8, typical number of non-redundant halfspaces is 100-300 and number of extreme points 30000-300000.
Qhull (qhalf) computes the halfspace intersection about a point by computing the convex hull of a dual transformation ["A simple case...", Preparata and Shamos, p. 316].
Does the computed convex hull distinguish between bounded and unbounded intersections?
As a temporary solution I suggested adding a large bounding box to the input data. If the corresponding halfspaces are non-redundant, then the intersection is clearly bounded. This test does not distinguish a unbounded intersection from a large, but bounded intersection.
Any suggestions for Marcin?
--Brad
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://compgeom.poly.edu/pipermail/compgeom-announce/attachments/20041203/28afd1e7/attachment.htm
More information about the Compgeom-announce
mailing list