Article View: sci.math.num-analysis
Article #667Polygon, a point in or out
From: samer Takriti
Date: Tue, 29 Sep 1992 13:30
Date: Tue, 29 Sep 1992 13:30
13 lines
1098 bytes
1098 bytes
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). Thanks. -Samer
Technical Details
Message-ID:
<5C1-w=_@engin.umich.edu>Path:
arc1-ca.pugleaf.net!sparky!uunet!haven.umd.edu!darwin.sura.net!spool.mu.edu!caen!takritiShow Full Headers
Complete Article Headers
Newsgroups: sci.math.num-analysis Path: arc1-ca.pugleaf.net!sparky!uunet!haven.umd.edu!darwin.sura.net!spool.mu.edu!caen!takriti From: takriti@engin.umich.edu (samer Takriti) Subject: Polygon, a point in or out Message-ID: <5C1-w=_@engin.umich.edu> Date: Tue, 29 Sep 92 09:30:09 EDT Organization: University of Michigan Engineering, Ann Arbor Nntp-Posting-Host: maize.engin.umich.edu Lines: 14