Proximity and reachability in the plane.
Der-Tsai Lee · Defense Technical Information Center (DTIC) · 1978
The Voronoi diagram for a set of N points in the Cartesian plane in which the L sub p-metric is the distance measure (p, 1 < or = p < or = infinity, is a real number) is defined and an algorithm for constructing the diagram in O(NlogN) time is presented. The notion of Voronoi diagram is also generalized to the case when we have a set of N disjoint line segments in the Euclidean plane. An O(N(log N)squared) algorithm for constructing the diagram is given. The method is applicable for the construction of the Voronoi diagram for a set of more complex figures, e.g., polygons and circles in the Euclidean plane. Furthermore, if the given line segments from a simple polygon, O(NlogN) time is sufficient. (Author)