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?
>
> --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.
More information about the Compgeom-announce
mailing list