Proximity and Reachability in the Plane.
Abstract
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1978
- Accession Number
- ADA069764
Entities
People
- Der-tsai Lee
Organizations
- University of Illinois Urbana–Champaign