Xref: utzoo comp.graphics:11380 sci.math.num-analysis:799 Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!samsung!xylogics!linus!bs From: bs@linus.UUCP (Robert D. Silverman) Newsgroups: comp.graphics,sci.math.num-analysis Subject: Re: Needed: Methods/heuristics for deterining if a point is in a Polytope Message-ID: <108669@linus.UUCP> Date: 8 May 90 12:32:52 GMT References: <35059@shemp.CS.UCLA.EDU> Reply-To: bs@gauss.UUCP (Robert D. Silverman) Organization: The MITRE Corporation, Bedford MA Lines: 26 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. -- Bob Silverman #include Mitre Corporation, Bedford, MA 01730 "You can lead a horse's ass to knowledge, but you can't make him think"