krishna@cs.tamu.edu (Krishna Kumar) (01/22/91)
Can anyone out there tell me what the current status of the following problem is ? INPUT : A polygon P QN : Is P simple (i.e Do any two edges of P intersect other than at a vertex) Preparata and Shamos describe an O( nlogn ) algorithm. Has anything better been done recently? Alternatively is there a non-trivial lower bound known for the problem? Krishna Kumar Dept. of Computer Science Texas A&M University College Station, TX 77840
eppstein@wormwood.ics.uci.edu (David Eppstein) (01/23/91)
In article <11430@helios.TAMU.EDU> krishna@cs.tamu.edu (Krishna Kumar) writes: > Can anyone out there tell me the current status of the following problem? > > INPUT : A polygon P > QN : Is P simple (Do any two edges of P intersect other than at a vertex) This can be done in linear time -- compute the convex hull, triangulate the interior and the "indentations" between the polygon and its hull using Chazelle's algorithm, and test if you really have a triangulation of a convex region. Of course if you're looking for a practical algorithm, this is not the way... -- David Eppstein UC Irvine, Info & Computer Science eppstein@ics.uci.edu