Finding the Constrained Delaunay Triangulation and Constrained Voronoi Diagram of a Simple Polygon in Linear Time
F.P.S. Chin, Cao An Wang · SIAM Journal on Computing · 1998
In this paper, we present an $\Theta (n)$ time worst-case deterministic algorithm for finding the constrained Delaunay triangulation and constrained Voronoi diagram of a simple n-sided polygon in the plane. Up to now, only an O(n log n) worst-case deterministic and an O(n) expected time bound have been shown, leaving an O(n) deterministic solution open to conjecture.