Xref: utzoo comp.graphics:11364 sci.math.num-analysis:796
Path: utzoo!utgpu!news-server.csri.toronto.edu!clyde.concordia.ca!uunet!cs.utexas.edu!usc!elroy.jpl.nasa.gov!ucla-cs!rosen@lanai.cs.ucla.edu
From: rosen@lanai.cs.ucla.edu (Bruce E Rosen)
Newsgroups: comp.graphics,sci.math.num-analysis
Subject: Needed: Methods/heuristics for deterining if a point is in a Polytope
Message-ID: <35059@shemp.CS.UCLA.EDU>
Date: 7 May 90 19:55:19 GMT
Sender: news@CS.UCLA.EDU
Organization: UCLA Computer Science Department
Lines: 16

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
could be incorporated.  
	Thanks
	bruce