A point in a polyhedron: in or out. Using Linear Programming

Article View: sci.math.num-analysis

Article #678

Back to sci.math.num-analysis Previous Next

#678

From: samer Takriti
Date: Wed, 30 Sep 1992 13:47

13 lines
1143 bytes

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

Technical Details

Message-ID: <jg1-wr=@engin.umich.edu>

Path: arc1-ca.pugleaf.net!sparky!uunet!caen!takriti

Show Full Headers

Complete Article Headers

Newsgroups: sci.math.num-analysis
Path: arc1-ca.pugleaf.net!sparky!uunet!caen!takriti
From: takriti@engin.umich.edu (samer Takriti)
Subject: A point in a polyhedron: in or out. Using Linear Programming
Message-ID: <jg1-wr=@engin.umich.edu>
Date: Wed, 30 Sep 92 09:47:37 EDT
Organization: University of Michigan Engineering, Ann Arbor
Nntp-Posting-Host: ephedra.engin.umich.edu
Lines: 13