Xref: utzoo comp.graphics:11385 sci.math.num-analysis:801
Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!cs.utexas.edu!helios!gordon
From: gordon@cs.tamu.edu (Dan Gordon)
Newsgroups: comp.graphics,sci.math.num-analysis
Subject: Re: Needed: Methods/heuristics for deterining if a point is in a Polytope
Message-ID: <5267@helios.TAMU.EDU>
Date: 8 May 90 19:21:40 GMT
References: <35059@shemp.CS.UCLA.EDU} <108669@linus.UUCP>
Sender: usenet@helios.TAMU.EDU
Followup-To: comp.graphics
Organization: Computer Science Department, Texas A&M University
Lines: 32

In article <108669@linus.UUCP} bs@gauss.UUCP (Robert D. Silverman) writes:
}In article <35059@shemp.CS.UCLA.EDU> rosen@lanai.cs.ucla.edu (Bruce E Rosen) writes:
}:I would appreciate it if anyone could send me methods and heuristics
}:to determine if a point is inside a general n dimensional polytope.  These
}:methods need not be efficient. More specifically, 
}:	given an n dimensional polytope (convex or concave) consisting of
}:	2^n verticies, each vertex being an n dimensional vector.
}:	Determine if a point (n dim.) lies within the volume
}:	of the polytope.
}:For example, one method that is easy to compute might be to determine
}:if the point lies within an inner bounding rectangular prism inside
}:of the polytope. If the point lies within the prism, it lies within
}:the polytope.  This method is easy to program and quick, yet if the
}:point lies outside the prism, it could still lie within the polytope.
}:In that case, a second more reliable (albeit less efficient) method
} 
}This is simply the feasibility problem for linear programming: does
}a system of linear inequalities have a solution? 
}
}Karmarkar's algorithm solves this in polynomial time. Other techniques
}[e.g. Khachian's, Simplex] work also.

It is not the feasibility problem for linear programming for 2 reasons:

1. The input is not a set of half-spaces (linear inequalities) but a 
   set of points.

2. We are not asked if the convex hull is empty or non-empty (as in 
   the feasibility problem). Instead, we are given an additional point
   and we are asked if the point is in the convex hull of the others.
   Note that the convex hull of a (non-empty) set of points is always
   non-empty, so the feasibility problem here is trivial.