The Furthest-Site Geodesic Voronoi Diagram (Classic Reprint)

Excerpt from The Furthest-Site Geodesic Voronoi Diagram
A common goal of much recent research in computational geometry is to extend algorithms that have been developed for the Euclidean metric to the more complicated geodesic metric inside a simple polygon. The geodesic distance between two points in a simple polygon is the length of the shortest path connecting the points that remains inside the polygon. For example, Toussaint T86] gives an algorithm for the "relative convex hull" of a set of points inside a simple polygon; Aronov A87] gives an algorithm for the nearest-neighbor geodesic Voronoi diagram; and Pollack, Sharir and Rote PSR87] give an algorithm for the "geodesic center" of a simple polygon.
A classic structure in the Euclidean metric is the "furthest-site Voronoi diagram." Given a finite collection of point sites in the plane, the furthest-site Voronoi diagram partitions the plane into Voronoi cells, one cell per site. The site that owns a cell is the site that is furthest from every point in the cell. Using well-known algorithms, the Euclidean furthest-site Voronoi diagram of k sites can be computed in time O (k lo g k) and space O (k) PS85].
The content of this paper is an efficient algorithm for computing the furthest-site Voronoi diagram, defined by the geodesic metric inside a simple polygon. The algorithm uses O ((n + k) log (n + k)) time and O (n + k) space, where n is the number of bounding edges of the polygon and k is the number of sites. The best previous algorithm for this problem had running time O (n- log log n) AT86], and just computed (a superset of) the vertices of the furthest-site Voronoi diagram of the n corners of the polygon. We remark that our furthest-site geodesic Voronoi diagram algorithm is a factor of O (log n) faster than the best known nearest-site geodesic Voronoi diagram algorithm A87].
About the Publisher
Forgotten Books publishes hundreds of thousands of rare and classic books. Find more at www.forgottenbooks.com
This book is a reproduction of an important historical work. Forgotten Books uses state-of-the-art technology to digitally reconstruct the work, preserving the original format whilst repairing imperfections present in the aged copy. In rare cases, an imperfection in the original, such as a blemish or missing page, may be replicated in our edition. We do, however, repair the vast majority of imperfections successfully; any imperfections that remain are intentionally left to preserve the state of such historical works.