🚀 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