Is a halfspace intersection unbounded?

Brad Barber bradb at
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?

-------------- next part --------------
An HTML attachment was scrubbed...

More information about the Compgeom-announce mailing list