FINDING THE CONSTRAINED DELAUNAY TRIANGULATION AND CONSTRAINED VORONOI DIAGRAM OF A SIMPLE POLYGON IN LINEAR-TIME

Authors
CHIN F WANG CA
Citation
F. Chin et Ca. Wang, FINDING THE CONSTRAINED DELAUNAY TRIANGULATION AND CONSTRAINED VORONOI DIAGRAM OF A SIMPLE POLYGON IN LINEAR-TIME, SIAM journal on computing (Print), 28(2), 1999, pp. 472-487
Citations number
21
Categorie Soggetti
Computer Science Theory & Methods",Mathematics,"Computer Science Theory & Methods",Mathematics
Journal title
SIAM journal on computing (Print) → ACNP
ISSN journal
00975397
Volume
28
Issue
2
Year of publication
1999
Pages
472 - 487
Database
ISI
SICI code
0097-5397(1999)28:2<472:FTCDTA>2.0.ZU;2-Y
Abstract
In this paper, we present an Theta(n) time worst-case deterministic al gorithm for finding the constrained Delaunay triangulation and constra ined Voronoi diagram of a simple n-sided polygon in the plane. Up to n ow, only an O(n log n) worst-case deterministic and an O(n) expected t ime bound have been shown, leaving an O(n) deterministic solution open to conjecture.