×

Zone diagrams in compact subsets of uniformly convex normed spaces. (English) Zbl 1256.52003

Summary: A zone diagram is a relatively new concept which has emerged in computational geometry and is related to Voronoi diagrams. Formally, it is a fixed point of a certain mapping, and neither its uniqueness nor its existence are obvious in advance. It has been studied by several authors, starting with T. Asano, J. Matoušek and T. Tokuyama, who considered the Euclidean plane with singleton sites, and proved the existence and uniqueness of zone diagrams there. In the present paper we prove the existence of zone diagrams with respect to finitely many pairwise disjoint compact sites contained in a compact and convex subset of a uniformly convex normed space, provided that either the sites or the convex subset satisfy a certain mild condition. The proof is based on the Schauder fixed point theorem, the Curtis-Schori theorem regarding the Hilbert cube, and on recent results concerning the characterization of Voronoi cells as a collection of line segments and their geometric stability with respect to small changes of the corresponding sites. Along the way we obtain the continuity of the Dom mapping as well as interesting and apparently new properties of Voronoi cells.

MSC:

52A21 Convexity and finite-dimensional Banach spaces (including special norms, zonoids, etc.) (aspects of convex geometry)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] T. Asano and D. Kirkpatrick, Distance trisector curves in regular convex distance metrics, Proceedings of the 3rd International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2006), pp. 8–17.
[2] T. Asano, J. Matoušek and T. Tokuyama, The distance trisector curve, Advances in Mathematics 212 (2007), 338–360, a preliminary version in STOC 2006, pp. 336–343. · Zbl 1185.68768 · doi:10.1016/j.aim.2006.10.006
[3] T. Asano, J. Matoušek and T. Tokuyama, Zone diagrams: Existence, uniqueness, and algorithmic challenge, SIAM Journal on Computing 37 (2007), 1182–1198, a preliminary version in SODA 2007, pp. 756–765. · Zbl 1156.68050 · doi:10.1137/06067095X
[4] T. Asano and T. Tokuyama, Drawing equally-spaced curves between two points, Abstracts of the 14th Annual Workshop on Computational Geometry with a Focus on Open Problems, 2004, pp. 24–25.
[5] F. Aurenhammer, Voronoi diagrams-a survey of a fundamental geometric data structure, ACM Computing Surveys, Vol. 3, 1991, pp. 345–405. · doi:10.1145/116873.116880
[6] S. C. de Biasi, B. Kalantari and I. Kalantari, Maximal zone diagrams and their computation, Proceedings of the 7th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2010), pp. 171–180. · Zbl 1250.68279
[7] J. Chun, Y. Okada and T. Tokuyama, Distance trisector of segments and zone diagram of segments in a plane, Proceedings of the 4th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2007), pp. 66–73.
[8] J. A. Clarkson, Uniformly convex spaces, Transactions of the American Mathematical Society 40 (1936), 396–414. · JFM 62.0460.04 · doi:10.1090/S0002-9947-1936-1501880-4
[9] D. W. Curtis and R. M. Schori, Hyperspaces of Peano continua are Hilbert cubes, Fundamenta Mathematicae 101 (1978), 19–38. · Zbl 0409.54044
[10] J. Dugundji and A. Granas, Fixed Point Theory, Springer Monographs in Mathematics, Springer-Verlag, New York, 2003. · Zbl 1025.47002
[11] K. Goebel and S. Reich, Uniform Convexity, Hyperbolic Geometry, and Nonexpansive Mappings, Monographs and Textbooks in Pure and AppliedMathematics, Vol. 83, Marcel Dekker Inc., New York, 1984.
[12] C. Gold, The Voronoi Web Site, http://www.voronoi.com/wiki/index.php?title=MainPage .
[13] A. Illanes and S. B. Nadler Jr, Hyperspaces. Fundamentals and Recent Advances, Monographs and Textbooks in Pure and Applied Mathematics, Vol. 216, Marcel Dekker Inc., New York, 1999. · Zbl 0933.54009
[14] K. Imai, A. Kawamura, J. Matoušek, Y. Muramatsu and T. Tokuyama, Distance ksectors and zone diagrams, Extended abstract in EuroCG 2009, pp. 191–194. Available at http://www.cs.toronto.edu/?kawamura/publ/090317 .
[15] A. Kawamura, J. Matoušek and T. Tokuyama, Zone diagrams in Euclidean spaces and in other normed spaces, Mathematische Annalen, to appear. arXiv 0912.3016 (2009), a short version in SoCG 2010, pp. 216–221.
[16] J. Lindenstrauss and L. Tzafriri, Classical Banach Spaces, II: Function Spaces, Springer, Berlin, 1979. · Zbl 0403.46022
[17] J. Munkres, Topology, second ed., Prentice Hall, Upper Saddle River, NJ, 2000.
[18] A. Okabe, B. Boots, K. Sugihara and S. N. Chiu, Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, second ed., Wiley Series in Probability and Statistics, John Wiley & Sons Ltd., Chichester, 2000, with a foreword by D. G. Kendall. · Zbl 0946.68144
[19] D. Reem, An algorithm for computing Voronoi diagrams of general generators in general normed spaces, Proceedings of the 6th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2009), pp. 144–152.
[20] D. Reem, Voronoi and zone diagrams, Ph.D. thesis, The Technion-Israel Institute of Technology, 2010.
[21] D. Reem, the geometric stability of Voronoi diagrams with respect to small changes of the sites, arXiv 1103.4125. · Zbl 1283.68377
[22] D. Reem and S. Reich, Zone and double zone diagrams in abstract spaces, Colloquium Mathematicum 115 (2009), 129–145, arXiv 0708.2668 (2007). · Zbl 1165.51006 · doi:10.4064/cm115-1-11
[23] J. Schauder, Der Fixpunktsatz in Funktionalräumen, Studia Mathematica 2 (1930), 171–180. · JFM 56.0355.01
[24] T. Zamfirescu, Typical starshaped sets, Aequationes Mathematicae 36 (1988), 188–200. · Zbl 0661.52004 · doi:10.1007/BF01836090
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.