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
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.