Abstract
Given a set S of s points in the plane, where do we place a new point, p, in order to maximize the area of its region in the Voronoi diagram of S and p? We study the case where the Voronoi neighbors of p are in convex position, and prove that there is at most one local maximum.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Hee-Kap Ahn, Siu-Wing Cheng, Otfried Cheong, Mordecai Golin, and René van Oostrum. Competitive facility location along a highway. Proc. 7th Annu. Int. Conf. (COCOON 2001), Lecture Notes Comput. Sci.(2108):237–246, 2001.
Franz Aurenhammer and Rolf Klein. Voronoi diagrams. In Jörg-Rüdiger Sack and Jorge Urrutia, editors, Handbook of Computational Geometry, pages 201–290. Elsevier Science Publishers B.V. North-Holland, Amsterdam, 2000.
Otfried Cheong, Sariel Har-Peled, Nathan Linial, and Jiří Matoušek. The one-und Voronoi game. Proc. 18th Annu. ACM Symp. on Computational Geometry, 2002.
S. Fortune. Voronoi diagrams and Delaunay triangulations. In Jacob E. Goodman and Joseph O’Rourke, editors, Handbook of Discrete and Computational Geometry, chapter 20, pages 377–388. CRC Press LLC, Boca Raton, FL, 1997.
Atsuyuki Okabe and M. Aoyagi. Existence of equilibrium configurations of competitive firms on an infinite two-dimensional space. J. of Urban Economics, 29:349–370, 1991.
Atsuyuki Okabe, Barry Boots, Kokichi Sugihara, and Sung Nok Chiu. Spatial Tessellations: Concepts and Applications of Voronoi Diagrams. John Wiley & Sons, Chichester, UK, 2000.
B. Piper. Properties of local coordinates based on dirichlet tessellations. Computing Suppl., 8:227–239, 1993.
Micha Sharir and P. K. Agarwal. Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press, New York, 1995.
R. Sibson. A Brief Description of the Natural Neighbor Interpolant. In: D.V. Barnett (ed.) Interpolation Multiariate Data. Wiley, 1981.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dehne, F., Klein, R., Seidel, R. (2002). Maximizing a Voronoi Region: The Convex Case. In: Bose, P., Morin, P. (eds) Algorithms and Computation. ISAAC 2002. Lecture Notes in Computer Science, vol 2518. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36136-7_54
Download citation
DOI: https://doi.org/10.1007/3-540-36136-7_54
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00142-3
Online ISBN: 978-3-540-36136-7
eBook Packages: Springer Book Archive