Tentative prune-and-search for computing Voronoi vertices
David G. Kirkpatrick, Jack Scott Snoeyink · 1993
This paper gives optimal logarithmic-time algorithms for two problems related to computing vertices of Voronoi diagrams in the plane: 1) given a convex polygon, compute the largest homothet of a given triangle that can be inscribed in the polygon and 2) given three disjoint convex polygons, compute the points that are equidistant from all three. These algorithms are based on a prune-and-search technique that may make tentative discards that are later revoked or certified. In three dimensions, a general strategy using hierarchical data structures leads to poly-logarithmic algorithms for related problems.