×

Voronoi diagrams on the sphere. (English) Zbl 1071.65021

Summary: Given a set of compact sites on a sphere, we show that their spherical Voronoi diagram can be computed by computing two planar Voronoi diagrams of suitably transformed sites in the plane. We also show that a planar furthest-site Voronoi diagram can always be obtained as a portion of a nearest-site Voronoi diagram of a set of transformed sites. Two immediate applications are an O(\(n\log n\)) algorithm for the spherical Voronoi diagram of a set of circular arcs on the sphere, and an O(\(n\log n\)) algorithm for the furthest-site Voronoi diagram for a set of circular arcs in the plane.

MSC:

65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alt, H.; Schwarzkopf, O., The Voronoi diagram of curved objects, (Proc. 11th Annu. ACM Symposium on Computation Geometry (1995)), 89-97
[2] Augenbaum, J. M.; Peskin, C. S., On the construction of the Voronoi mesh on the sphere, J. Comput. Phys., 59, 177-192 (1985) · Zbl 0628.65115
[3] Aurenhammer, F., Voronoi diagrams: a survey of a fundamental geometric data structure, ACM Comput. Surv., 23, 345-405 (1991)
[4] Aurenhammer, F.; Schwarzkopf, O., A simple on-line randomized incremental algorithm for computing higher order Voronoi diagrams, Internat. J. Comput. Geom. Appl., 2, 363-381 (1992) · Zbl 0803.68131
[5] K.Q. Brown, Geometric transforms for fast geometric algorithms, Ph.D. Dissertation, Carnegie-Mellon Univ., 1980, pp. 73-75; K.Q. Brown, Geometric transforms for fast geometric algorithms, Ph.D. Dissertation, Carnegie-Mellon Univ., 1980, pp. 73-75
[6] Brown, K. Q., Voronoi diagrams from convex hulls, Inform. Process. Lett., 9, 223-228 (1979) · Zbl 0424.68036
[7] Choi, H. I.; Choi, S. W.; Moon, H. P., Mathematical theory of medial axis transform, Pacific J. Math., 181, 57-88 (1997) · Zbl 0885.53004
[8] Choi, H. I.; Choi, S. W.; Moon, H. P.; Wee, N. S., New algorithm for medial axis transform of plane domain, Graphical Models and Image Processing, 59, 463-483 (1997)
[9] Dodge, C. W., Euclidean Geometry and Transformations (1972), Addison-Wesley
[10] Farouki, R. T.; Johnstone, J. K., The bisector of a point and a plane parametric curve, Computer Aided Geometric Design, 11, 117-151 (1994) · Zbl 0796.65013
[11] Fortune, S. J., A sweepline algorithm for Voronoi diagrams, Algorithmica, 2, 153-174 (1987) · Zbl 0642.68079
[12] Klein, R., Concrete and Abstract Voronoi Diagrams. Concrete and Abstract Voronoi Diagrams, Lecture Notes in Computer Science, 400 (1989), Springer-Verlag · Zbl 0699.68005
[13] Klein, R.; Mehlhorn, K.; Meiser, S., Randomized incremental construction of abstract Voronoi diagrams, Computational Geometry, 3, 157-184 (1993) · Zbl 0797.68153
[14] H.S. Na, C.N. Lee, O. Cheong, Randomized incremental construction of spherical Voronoi diagram for points and circular arcs, Manuscript, 1998; H.S. Na, C.N. Lee, O. Cheong, Randomized incremental construction of spherical Voronoi diagram for points and circular arcs, Manuscript, 1998
[15] Okabe, A.; Boots, B.; Sugihara, K., Spatial Tessellations: Concepts and Applications of Voronoi Diagrams (1992), Wiley · Zbl 0877.52010
[16] Preparata, F. P.; Shamos, M. I., Computational Geometry: An Introduction (1985), Springer-Verlag, pp. 15-17
[17] Ramamurthy, R.; Farouki, R. T., Voronoi diagram and medial axis algorithm for planar domains with curved boundaries: I. Theoretical foundations, J. Comput. Appl. Math., 102, 117 (1999) · Zbl 0939.65018
[18] Ramamurthy, R.; Farouki, R. T., Specified-precision computation of curve/curve bisectors, Internat. J. Comput. Geom. Appl., 8, 599-619 (1998) · Zbl 1026.65010
[19] Rausch, T.; Wolter, F. E.; Sniehotta, O., Computation of medial curves on surfaces, The Mathematics of Surfaces, VII, 43-68 (1997) · Zbl 0965.65021
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.