Voronoi diagrams for convex polygon-offset distance functions

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.