Voronoi Diagram in the Laguerre Geometry and Its Applications
Citations Over TimeTop 10% of 1985 papers
Abstract
We extend the concept of Voronoi diagram in the ordinary Euclidean geometry for n points to the one in the Laguerre geometry for n circles in the plane, where the distance between a circle and a point is defined by the length of the tangent line, and show that there is an $O(n\log n)$ algorithm for this extended case. The Voronoi diagram in the Laguerre geometry may be applied to solving effectively a number of geometrical problems such as those of determining whether or not a point belongs to the union of n circles, of finding the connected components of n circles, and of finding the contour of the union of n circles. As in the case with ordinary Voronoi diagrams, the algorithms proposed here for those problems are optimal to within a constant factor. Some extensions of the problem and the algorithm from different viewpoints are also suggested.
Related Papers
- → Quasi-triangulation and interworld data structure in three dimensions(2006)73 cited
- → Simplified Voronoi diagrams(1987)76 cited
- Open source implementation of the Multiplicatively Weighted Voronoi Diagram as a TerraView plugin(2011)
- Euclidean proximity and power diagrams.(1998)
- Thought of Drawing Weighted Voronoi Diagram with 1-order Neighbor(2008)