Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!uunet!cs.utexas.edu!helios!cs.tamu.edu
From: krishna@cs.tamu.edu (Krishna Kumar)
Newsgroups: comp.theory
Subject: SIMPLICITY TEST for polygons
Message-ID: <11430@helios.TAMU.EDU>
Date: 22 Jan 91 15:22:59 GMT
Sender: usenet@helios.TAMU.EDU
Organization: Computer Science Department, Texas A&M University
Lines: 15


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