Is a halfspace intersection unbounded?

Brad Barber bradb at
Sun Dec 12 17:57:42 PST 2004

[With Steven Spitz]

Qhull computes halfspace intersection about a point by computing the convex hull of the dual vertices.  Halfspaces at distance d from the origin are dual to vertices at distance 1/d.  So the bounding box at infinity is equivalent to the origin.  If the origin is inside the dual polytope, then the original polytope is bounded.  Otherwise it is either unbounded.

So in Qhull, boundedness is equivalent to every inner plane (option 'Fi') having a negative offset (the inner planes are clearly inside the dual polytope).  Unboundedness is equivalent to at least one outer plane (option 'Fo') having a positive offset.  

If you do not need halfspace intersections, then Komei's LP solution is best.


The compgeom mailing lists: see
or send mail to compgeom-request at with the line:
send readme
Now archived at

More information about the Compgeom-announce mailing list