A linear-time algorithm for computing the voronoi diagram of a convex polygon |
| |
Authors: | Alok Aggarwal Leonidas J. Guibas James Saxe Peter W. Shor |
| |
Affiliation: | (1) IBM T. J. Watson Research Center, P.O. Box 218, 10598 Yorktown Heights, NY, USA;(2) Department of Computer Science, Stanford University, 94305 Stanford, CA, USA;(3) DEC Systems Research Center, 130 Lytton Avenue, 94301 Palo Alto, CA, USA;(4) AT&T Bell Laboratories, 600 Mountain Avenue, 07974 Murray Hill, NJ, USA |
| |
Abstract: | We present an algorithm for computing certain kinds of three-dimensional convex hulls in linear time. Using this algorithm, we show that the Voronoi diagram ofn sites in the plane can be computed in (n) time when these sites form the vertices of a convex polygon in, say, counterclockwise order. This settles an open problem in computational geometry. Our techniques can also be used to obtain linear-time algorithms for computing the furthest-site Voronoi diagram and the medial axis of a convex polygon and for deleting a site from a general planar Voronoi diagram.This research began while the first and fourth authors were visiting the Mathematical Sciences Research Institute in Berkeley, California. Work by the fourth author was supported in part by NSF Grant No. 8120790. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|