Is a halfspace intersection unbounded?

[Brad Barber]

[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.

					--Brad


-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.