Voronoi diagrams for convex polygon-offset distance functions |
| |
Authors: | G. Barequet M. T. Dickerson M. T. Goodrich |
| |
Affiliation: | (1) Center for Geometric Computing, Department of Computer Science, Johns Hopkins University, Baltimore, MD 21218, USA {barequet, goodrich}@cs.jhu.edu , US;(2) Department of Mathematics and Computer Science, Middlebury College, Middlebury, VT 05753, USA dickerso@middlebury.edu, US |
| |
Abstract: | In this paper we develop the concept of a convex polygon-offset distance function. Using offset as a notion of distance, we show how to compute the corresponding nearest- and furthest-site Voronoi diagrams of point sites in the plane. We provide near-optimal deterministic O (n (log n + log 2 m) + m) -time algorithms, where n is the number of points and m is the complexity of the underlying polygon, for computing compact representations of both diagrams. Received January 8, 1999, and in revised form January 5, 2000, and June 12, 2000. Online publication December 4, 2000. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|