Is a halfspace intersection unbounded?

Komei Fukuda fukuda at
Sun Dec 5 19:58:17 PST 2004


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 

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

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
or send mail to compgeom-request at with the line:
send readme
Now archived at

More information about the Compgeom-announce mailing list