|
 ABSTRACT
We present an “expanding waves” view of Voronoi diagrams that allows such diagrams to be defined for very general metrics and for distance measures that do not qualify as metrics. If a pebble is dropped into a still pond, circular waves move out from the point of impact. If n pebbles are dropped simultaneously, the places where wave fronts meet define the Voronoi diagram on the n points of impact.
The Voronoi diagram for any normed metric, including the Lp metrics, can be obtained by changing the shape of the wave front from a circle to the shape of the “circle” in that metric. (For example, the “circle” in the L1 metric is diamond shaped.) For any convex wave shape there is a corresponding convex distance function. If the shape is not symmetric about its center (a triangle, for example) then the resulting distance function is not a metric, although it can still be used to define a Voronoi diagram.
Like Voronoi diagrams based on the Euclidean metric, the Voronoi diagrams based on other normed metrics can be used to solve various closest-point problems (all-nearest-neighbors, minimum spanning trees, etc.). Some of these problems also make sense under convex distance functions which are not metrics. In particular, the “largest empty circle” problem becomes the “largest empty convex shape” problem, and “motion planning for a disc” becomes “motion planning for a convex shape”. These problems can both be solved quickly given the Voronoi diagram. We present an asymptotically optimal algorithm for computing Voronoi diagrams based on convex distance functions.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
[Ca59] J. W. S. Cassels, An Introduction to the Geometry of Numbers, Springer-Verlag, Berlin (1959).
|
| |
2
|
|
| |
3
|
|
 |
4
|
|
| |
5
|
[Ki79] D. G. Kirkpatrick, Efficient Computation of Continuous Skeletons, Proc. 20th IEEE Symposium on Foundations of Computer Science, 1979, 18-27.
|
| |
6
|
[KN63] J. L. Kelley and I. Namioka, Linear Topological Spaces, Van Nostrand, Princeton (1963).
|
| |
7
|
[Kn73] D. E. Knuth, The Art of Computer Programming, vol. 3, Addison-Wesley, Reading, MA (1973).
|
| |
8
|
[La72] S. R. Lay, Convex Sets and their Applications, Wiley, New York (1972).
|
| |
9
|
|
| |
10
|
[Le82] D. T. Lee, On k-nearest neighbor Voronoi diagrams in the plane, IEEE TRANS. COMP. C-31 (1982), 478-487.
|
| |
11
|
[LW80] D. T. Lee and C. K. Wong, Voronoi diagrams in L1 (Linfinity) metrics with 2-dimensional storage applications, SIAM J. COMPUT. 9(1980), 200-211.
|
| |
12
|
|
| |
13
|
[SH75] M. I. Shamos and D. Hoey, Closest-Point Problems, Proc. 16th IEEE Symposium on Foundations of Computer Science, 1975, 151-162.
|
| |
14
|
[Ya84] C. K. Yap, An O(n log n) algorithm for the Voronoi diagram of a set of simple curve segments, Technical Report, Courant Institute, New York University, Oct. 1984.
|
CITED BY 39
|
|
|
|
|
Oswin Aichholzer , Danny Z. Chen , D. T. Lee , Asish Mukhopadhyay , Evanthia Papadopoulou , Franz Aurenhammer, Voronoi diagrams for direction-sensitive distances, Proceedings of the thirteenth annual symposium on Computational geometry, p.418-420, June 04-06, 1997, Nice, France
|
|
|
M. Abellanas , G. Hernandez , R. Klein , V. Neumann-Lara , J. Urrutia, Voronoi diagrams and containment of families of convex sets on the plane, Proceedings of the eleventh annual symposium on Computational geometry, p.71-78, June 05-07, 1995, Vancouver, British Columbia, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
A. Aggarwal , M. Hansen , T. Leighton, Solving query-retrieval problems by compacting Voronoi diagrams, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.331-340, May 13-17, 1990, Baltimore, Maryland, United States
|
|
|
L. Paul Chew , Klara Kedem , Micha Sharir , Boaz Tagansky , Emo Welzl, Voronoi diagrams of lines in 3-space under polyhedral convex distance functions, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.197-204, January 22-24, 1995, San Francisco, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Mark de Berg , Jiří Matoušek , Otfried Schwarzkopf, Piecewise linear paths among convex obstacles, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.505-514, May 16-18, 1993, San Diego, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Daniel P. Huttenlocher , Klara Kedem , Micha Sharir, The upper envelope of Voronoi surfaces and its applications, Proceedings of the seventh annual symposium on Computational geometry, p.194-203, June 10-12, 1991, North Conway, New Hampshire, United States
|
|
|
Christian Icking , Rolf Klein , Ngoc-Minh Lê , Lihong Ma, Convex distance functions in 3-space are different, Proceedings of the ninth annual symposium on Computational geometry, p.116-123, May 18-21, 1993, San Diego, California, United States
|
|
|
Li Zhang , Harish Devarajan , Julien Basch , Piotr Indyk, Probabilistic analysis for combinatorial functions of moving points, Proceedings of the thirteenth annual symposium on Computational geometry, p.442-444, June 04-06, 1997, Nice, France
|
|
|
A. Corbalan , M. Mazon , T. Recio , F. Santos, On the topological shape of planar Voronoi diagrams, Proceedings of the ninth annual symposium on Computational geometry, p.109-115, May 18-21, 1993, San Diego, California, United States
|
|
|
Christian Icking , Rolf Klein , Peter Köllner , Lihong Ma, Java applets for the dynamic visualization of Voronoi diagrams, Computer science in perspective, Springer-Verlag New York, Inc., New York, NY, 2003
|
|
|
|
|
|
Christian Icking , Rolf Klein , Lihong Ma , Stefan Nickel , Ansgar Weißler, On bisectors for different distance functions, Proceedings of the fifteenth annual symposium on Computational geometry, p.291-299, June 13-16, 1999, Miami Beach, Florida, United States
|
|
|
Boaz Ben-Moshe , Olaf Hall-Holt , Matthew J. Katz , Joseph S. B. Mitchell, Computing the visibility graph of points within a polygon, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA
|
|
|
|
|
|
|
|
|
|
|
|
Siu-Wing Cheng , Hyeon-Suk Na , Antoine Vigneron , Yajun Wang, Approximate shortest paths in anisotropic regions, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.766-774, January 07-09, 2007, New Orleans, Louisiana
|
|
|
|
|
|
|
|
|
|
|
|
Oswin Aichholzer , Wolfgang Aigner , Franz Aurenhammer , Thomas Hackl , Bert Jüttler , Elisabeth Pilgerstorfer , Margot Rabl, Divide-and-conquer for Voronoi diagrams revisited, Proceedings of the 25th annual symposium on Computational geometry, June 08-10, 2009, Aarhus, Denmark
|
|
|
Thomas Iwaszko , Mahmoud Melkemi , Lhassane Idoumghar, A theoretical structure for computational geometry: regions of point-free overlapping circles, Proceedings of the 9th WSEAS international conference on Signal processing, computational geometry and artificial vision, p.117-122, August 20-22, 2009, Moscow, Russia
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
I.3