Voronoi diagrams for convex polygon-offset distance functions
Voronoi diagrams for convex polygon-offset distance functions
复制标题
凸多边形偏移距离函数的 Voronoi 图
DOI：
--
复制
发表时间：
2001
影响因子：
0.8
通讯作者：
M. Goodrich
中科院分区：
文献类型：
--
作者：
G. Barequet;M. Dickerson;M. Goodrich
In this paper we develop the concept of a convexpolygon-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 deterministicO(n(logn + log2m) +m)-time algorithms, wheren is the number of points andm is the complexity of the underlying polygon, for computing compact representations of both diagrams.
