🚀 go-pugleaf

In article <5C1-w=_@engin.umich.edu>, takriti@engin.umich.edu (samer Takriti) writes:
|> I have received many answers referring to "Computational Geometry,
|> an introduction" by Preparata and Shamos. Thanks.
|> It looks to me that he methods proposed by this book can be applied
|> in R^2 only. Applying these methods in higher dimensions would 
|> increase the complexity of the algorithm (exponential complexity).
|> For instance, given n+1 points in R^m (n > m) and assume that the
|> origin is one of these points, the number of m-1 dimensional facets
|> of the convex hull is nCm which creates a combinatorial problem.
|> Is there a method that can check for the inclusion of a point in
|> a polytope in R^n that does not need an exponential time ? (I mean
|> methods that depend on ray shooting).

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.

The way to apply it to R^3 is to intersect the polyhedron with
a plane that passes through the point in question. Now construct a 
representation of the polygon of intersection. Now you can use the ray
shooting method or the binary search method. Constructing the polygon
I would think is O(n) in the number of vertices but I haven't really given
it much thought.

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

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.

Larry Edwards

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