Is a halfspace intersection unbounded?

[Komei Fukuda]

Hi,

Checking whether a polyhedral region is bounded or not
can be done by solving two linear programs (LPs).

Let  P = { x:  A x = b,  x >=0}, where A is a given m by d
matrix and b is a m-vector.  One can easily see

P is unbounded   <=>
   P is nonempty and there is a nonzero vector z such that  A z = 0 and 
z >= 0.

Let's assume P is nonempty (which can be checked
by a single LP).    Then,

P is unbounded
<=>   there is a nonzero vector z  such that  A z = 0 and  z >= 0
<=>   there is no  m-vector  y  such that   y^T  A  > 0  (totally 
positive).

The last equivalence is a variant of Farkas' Lemma.
The last condition can be checked by solving an LP:

max  alpha
    (y^T A)_j  >= alpha   for all j=1,...,d   and
    alpha   <= 1.

where alpha is a new variable.  Clearly, this LP has
a positive optimal value if and only if  P is bounded.

To deal with other forms of inequality sytems, e.g.  P ={ x :   A  x  
<= b},
one can use standard techniques of inequality transformations.

Because we only need to solve LPs,
unboundedness can be recognized very fast for large d  and  m
by both simplex-type methods and by interior-point methods.

I hope this helps,  Komei

---
Komei Fukuda <fukuda at ifor.math.ethz.ch>
Institute for Operations Research
and Institute of Theoretical Computer Science
ETH Zentrum, CH-8092 Zurich, Switzerland
Tel +41-1-632-4023, Fax +41-1-632-1025
http://www.ifor.math.ethz.ch/staff/fukuda/




On Dec 4, 2004, at 12:58 AM, Brad Barber wrote:

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


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