🚀 go-pugleaf

RetroBBS NetNews Server

Inspired by RockSolid Light RIP Retro Guy

Article View: sci.math.num-analysis
Article #667

Polygon, a point in or out

#667
From: samer Takriti
Date: Tue, 29 Sep 1992 13:30
13 lines
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!takriti

Show 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