Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!uunet!samsung!zaphod.mps.ohio-state.edu!usc!ucla-cs!ucivax!eppstein
From: eppstein@wormwood.ics.uci.edu (David Eppstein)
Newsgroups: comp.theory
Subject: Re: SIMPLICITY TEST for polygons
Message-ID: <279C78AC.8578@ics.uci.edu>
Date: 22 Jan 91 17:38:52 GMT
References: <11430@helios.TAMU.EDU>
Reply-To: eppstein@ics.uci.edu (David Eppstein)
Organization: UC Irvine Department of ICS
Lines: 14
Nntp-Posting-Host: wormwood.ics.uci.edu

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