A linear-time randomized algorithm for the bounded Voronoi diagram of a simple polygon
Rolf Klein, Andrzej Lingas · 1993
For a polygon P, the bounded Voronoi diagram of P is a partition of P into regions assigned to the vertices of P: A point p inside P belongs to the region of a vertex v if and only if v is the closest vertex of P visible from p. We present a randomized algorithm that builds the bounded Voronoi diagram of a simple polygon in linear expected time. Among other applications, we can construct within the same time bound the generalized Delaunay triangulation of P and the minimal spanning tree on P 's vertices that is contained in P.