🚀 go-pugleaf

In article <1992Oct1.005727.11567@leland.Stanford.EDU> ledwards@leland.Stanford.EDU (Laurence James Edwards) writes:
>[...]
>In article <jg1-wr=@engin.umich.edu>, takriti@engin.umich.edu (samer Takriti) writes:
>|> I asked a couple of days ago on how to apply the method described
>|> by Preparata and Shamos for a set of points in R^m, but I have not
>|> received a single answer. It looks that the methods described in this
>|> book can be applied to R^2 only.
>[...]
>|> When somebody asked this question a while ago, I suggested using 
>|> Linear Programming instead of "shooting" rays. A lot of people criticized
>|> Linear Programming because "the complexity of the method described 
>|> by Preparat and Shamos is O(n)". Well, solving a linear program with
>|> three constraints and n variables is O(n). So, again, I insist that
>|> using Linear Programming is better than "shooting rays" in the region
>|> specially that it gives the representation of the given point in terms
>|> of the corner points.
>|> -Samer
>
>I don't remember what the linear programming algorithm you gave was, but
>the simplex algorithm is worst case exponential in the number of dimensions
>and the number of constraints (faces). See "Algorithms in Combinatorial
>Geometry" by Edelsbrunner pg 238. A worst case polynomial time
>algorithm by Khachiyan is mentioned but it is not clear if there is a
>practical implementation.

First, Megiddo (in JACM 31, 1984) gives an algorithm that runs in time
linear in the number of constraints, if the number of dimensions is
fixed (if the number of constraints is fixed and the number of
variables is not, you can solve the dual.  Second, although the
worst-case running time of the simplex method is exponential, its
average running time is not.  It may very well do the job that Takriti
wants efficiently enough for his purposes (see below).  Third,
although Khachiyan's algorithm does not seem to be practical, Newton
barrier methods (related to Karmarkar's algorithm) are polynomial, and
are practical for many applications (but not necessarily this one).

>My somewhat shallow understanding of linear programming is that it gives you
>an extremal point on a polytope. The original question related to determining
>whether a point is in a polygon, finding a representation of the point was
>not in question, you already have it to start with.

Given a representation of a polytope as a system of inequalities, LP
can tell you if a feasible solution or nonnegative feasible solution
or a direction of unboundedness (wrt a linear cost function) exists,
find a feasible solution, find a nonnegative feasible solution find a
minimum-cost feasible solution (with a linear cost function).  Testing
whether a point is inside a polytope with this representation is
trivially easy--just test if your point satisfies all the inequalities.

If the representation is as the convex hull of extreme points and
rays, the story is a little different.  In this case, the system of
inequalities is to find a convex combination of extreme points and
positive combination of extreme rays that represents the point in
question.  This is also a LP, and its size is polynomially related to
the size of the inequality representation (if both representations are
minimal).  I think it is this method that Takriti has in mind.

>
>Larry Edwards


-- 
		Matthew Saltzman
		Clemson University Math Sciences
		mjs@clemson.edu