# Is a halfspace intersection unbounded?

Komei Fukuda fukuda at ifor.math.ethz.ch
Sun Dec 5 19:58:17 PST 2004

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

-------------
The compgeom mailing lists: see