The edge labeling of higher order Voronoi diagrams. (English) Zbl 07925627
Summary: We present an edge labeling of order-\(k\) Voronoi diagrams, \(V_k (S)\), of point sets \(S\) in the plane, and study properties of the regions defined by them. Among them, we show that \(V_k (S)\) has a small orientable cycle and path double cover, and we identify configurations that cannot appear in \(V_k (S)\) for small values of \(k\). This paper also contains a systematic study of well-known and new properties of \(V_k (S)\), all whose proofs only rely on elementary geometric arguments in the plane. The maybe most comprehensive study of structural properties of \(V_k (S)\) was done by D.T. Lee (On \(k\)-nearest neighbor Voronoi diagrams in the plane) in 1982. Our work reviews and extends the list of properties of higher order Voronoi diagrams.
MSC:
| 90Cxx | Mathematical programming |
Keywords:
Voronoi diagram; higher order Voronoi diagram; double cover; edge labeling; alternating hexagonReferences:
| [1] | Shamos, M.I., Hoey, D.: Closest-point problems. In: 16th Annual Symposium on Foundations of Computer Science (SFCS 1975), pp. 151-162. IEEE (1975) |
| [2] | Okabe, A.; Boots, B.; Sugihara, K.; Chiu, SN, Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, 2000, Chichester: Wiley, Chichester · Zbl 0946.68144 · doi:10.1002/9780470317013 |
| [3] | Jiang, B.; Sun, Z.; Anderson, BDO; Lageman, C., Higher order mobile coverage control with applications to clustering of discrete sets, Automatica, 102, 27-33, 2019 · Zbl 1415.93020 · doi:10.1016/j.automatica.2018.12.028 |
| [4] | Qiu, C.; Shen, H.; Chen, K., An energy-efficient and distributed cooperation mechanism fork-coverage hole detection and healing in WSNs, IEEE Trans. Mob. Comput., 17, 6, 1247-1259, 2017 · doi:10.1109/TMC.2017.2767048 |
| [5] | Abu-Affash, AK; Carmi, P.; Katz, MJ; Morgenstern, G., Multi cover of a polygon minimizing the sum of areas, Int. J. Comput. Geom. Appl., 21, 6, 685-698, 2011 · Zbl 1251.68276 · doi:10.1142/S021819591100386X |
| [6] | O’Neil, P.; Wanner, T., Analyzing the squared distance-to-measure gradient flow system with k-order Voronoi diagrams, Discrete Comput. Geom., 61, 91-119, 2019 · Zbl 1411.65030 · doi:10.1007/s00454-018-0037-6 |
| [7] | Kallrath, J.; Ryu, J.; Song, C.; Lee, M.; Kim, DS, Near optimal minimal convex hulls of disks, J. Glob. Optim., 80, 551-594, 2021 · Zbl 1473.90129 · doi:10.1007/s10898-021-01002-5 |
| [8] | Aurenhammer, F., Voronoi diagrams—a survey of a fundamental geometric data structure, ACM Comput. Surv., 23, 3, 345-405, 1991 · doi:10.1145/116873.116880 |
| [9] | Lee, DT, On k-nearest neighbor Voronoi diagrams in the plane, IEEE Trans. Comput., 31, 478-487, 1982 · Zbl 0491.68062 |
| [10] | Dehne, F.; Diaz, J., An \(o(n^4)\) algorithm to construct all Voronoi diagrams for \(k\)-nearest neighbor searching in the Euclidean plane, Automata, Languages and Programming, 160-162, 1983, Berlin: Springer, Berlin · doi:10.1007/BFb0036906 |
| [11] | Edelsbrunner, H., Algorithms in Combinatorial Geometry, 1987, Berlin: Springer, Berlin · Zbl 0634.52001 · doi:10.1007/978-3-642-61568-9 |
| [12] | Edelsbrunner, H.; Iglesias-Ham, M., Multiple covers with balls I: inclusion-exclusion, Comput. Geom. Theory Appl., 68, 119-133, 2018 · Zbl 1396.65039 · doi:10.1016/j.comgeo.2017.06.014 |
| [13] | El Oraiby, W.; Schmit, D.; Spehner, JC, Centroid triangulations from k-sets, Int. J. Comput. Geom. Appl., 21, 635-659, 2011 · Zbl 1251.68286 · doi:10.1142/S0218195911003846 |
| [14] | Lindenbergh, RC, A Voronoi poset, J. Geom. Graph., 7, 41-52, 2003 · Zbl 1056.52008 |
| [15] | Martínez-Legaz, JE; Roschina, V.; Todorov, M., On the structure of higher order Voronoi cells, J. Optim. Theory Appl., 183, 24-49, 2019 · Zbl 1434.52024 · doi:10.1007/s10957-019-01555-2 |
| [16] | Miles, RE; Maillardet, RJ, Basic structures of Voronoi and generalized Voronoi polygons, J. Appl. Probab., 19, 97-111, 1982 · Zbl 0482.60015 · doi:10.2307/3213553 |
| [17] | Schmitt, D., Spehner, J.C.: Order-k Voronoi diagrams, k-sections, and k-sets. In: Japanese Conference on Discrete and Computational Geometry 1998, Lecture Notes in Computer Science, pp. 290-304 (1999) · Zbl 0957.68121 |
| [18] | Liu, CH; Papadopoulou, E.; Lee, DT, The k-nearest-neighbor Voronoi diagram revisted, Algorithmica, 71, 429-449, 2015 · Zbl 1315.68255 · doi:10.1007/s00453-013-9809-9 |
| [19] | Chan, TM, Random sampling, halfspace range reporting, and construction of \(\backslash\) lowercase \(( \le )\)-levels in three dimensions, SIAM J. Comput., 30, 561-575, 2000 · Zbl 0963.68207 · doi:10.1137/S0097539798349188 |
| [20] | Chazelle, B., Edelsbrunner, H.: An improved algorithm for constructing kth-order Voronoi diagrams. In: Proceedings of the First Annual Symposium on Computational Geometry, pp. 228-234 (1985) |
| [21] | Edelsbrunner, H.; O’Rourke, J.; Seidel, R., Constructing arrangements of lines and hyperplanes with applications, SIAM J. Comput., 15, 2, 341-363, 1986 · Zbl 0603.68104 · doi:10.1137/0215024 |
| [22] | Aggarwal, A., Guibas, L., Saxe, J., Shor, P.: A linear time algorithm for computing the Voronoi diagram of a convex polygon. In: Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, pp. 39-45 (1987) |
| [23] | Clarkson, K.L.: Applications of random sampling in computational geometry, II. In: Proceedings of the Fourth Annual Symposium on Computational Geometry, pp. 1-11 (1988) |
| [24] | Aurenhammer, F., A new duality result concerning Voronoi diagrams, Discrete Comput. Geom., 5, 243-254, 1990 · Zbl 0693.68023 · doi:10.1007/BF02187788 |
| [25] | Agarwal, MJ, Dynamic half-space range reporting and its applications, Algorithmica, 13, 4, 325-345, 1995 · Zbl 0827.68037 · doi:10.1007/BF01293483 |
| [26] | Clarkson, KL, New applications of random sampling in computational geometry, Discrete Comput. Geom., 2, 195-222, 1987 · Zbl 0615.68037 · doi:10.1007/BF02187879 |
| [27] | Mulmuley, K., On levels in arrangements and Voronoi diagrams, Discrete Comput. Geom., 6, 307-338, 1991 · Zbl 0727.68129 · doi:10.1007/BF02574692 |
| [28] | Agarwal, P.K., De Berg, M., Matoušek, J., Schwarzkopf, O.: Constructing levels in arrangements and higher order Voronoi diagrams. In: Proceedings of the Tenth Annual Symposium on Computational Geometry, pp. 67-75 (1994) |
| [29] | Ramos, E.A.: On range reporting, ray shooting and k-level construction. In: Proceedings of the Fifteenth Annual Symposium on Computational Geometry, pp. 390-399 (1999) |
| [30] | Boissonnat, J-D; Devillers, O.; Teillaud, M., A semidynamic construction of higher-order Voronoi diagrams and its randomized analysis, Algorithmica, 9, 329-356, 1993 · Zbl 0780.68109 · doi:10.1007/BF01228508 |
| [31] | Aurenhammer, F., Schwarzkopf, O.: A simple on-line randomized incremental algorithm for computing higher order Voronoi diagrams. In: Proceedings of the Seventh Annual Symposium on Computational Geometry, pp. 142-151 (1991) |
| [32] | Jones, GA, Geometric and asymptotic properties of Brillouin zones in lattices, Bull. Lond. Math. Soc., 16, 241-263, 1984 · Zbl 0508.51015 · doi:10.1112/blms/16.3.241 |
| [33] | Veerman, JJP; Peixoto, MM; Rochal, AC; Sutherland, S., On Brillouin zones, Commun. Math. Phys., 212, 725-744, 2000 · Zbl 0979.53044 · doi:10.1007/PL00020959 |
| [34] | Tóth, GF, Multiple packing and covering of the plane with circles, Acta Math. Acad. Sci. Hung., 27, 135-140, 1976 · Zbl 0335.52010 · doi:10.1007/BF01896768 |
| [35] | Jaeger, F., A survey on the cycle double cover conjecture, Ann. Discrete Math., 27, 1-12, 1985 · Zbl 0585.05012 |
| [36] | Bondy, JA; Hahn, G.; Sabidussi, G.; Woodrow, RE, Small cycle double covers of graphs, Circles and Rays, 21-40, 1990, Dordrecht: Springer, Dordrecht · Zbl 0734.05067 · doi:10.1007/978-94-009-0517-7_4 |
| [37] | Seyffarth, K., Small cycle double covers of 4-connected planar graphs, Combinatorica, 13, 477-482, 1993 · Zbl 0794.05058 · doi:10.1007/BF01303519 |
| [38] | Seyffarth, K., Hajós conjecture and small cycle double covers of planar graphs, Discrete Math., 101, 291-306, 1992 · Zbl 0766.05067 · doi:10.1016/0012-365X(92)90610-R |
| [39] | Edelsbrunner, H.; Seidel, R., Voronoi diagrams and arrangements, Discrete Comput. Geom., 1, 25-44, 1986 · Zbl 0598.52013 · doi:10.1007/BF02187681 |
| [40] | de las Heras Parrilla, A.: Properties for Voronoi Diagrams of Arbitrary Order in the Sphere. Master Thesis. Universitat Politècnica de Catalunya (2021). https://upcommons.upc.edu/handle/2117/354664 |
| [41] | Bohler, C.; Cheilaris, P.; Klein, R.; Liu, CH; Papadopoulou, E.; Zavershynskyi, M., On the complexity of higher order abstract Voronoi diagrams, Comput. Geom., 48, 8, 539-551, 2015 · Zbl 1396.65033 · doi:10.1016/j.comgeo.2015.04.008 |
| [42] | Bohler, C.; Klein, R.; Liu, CH, An efficient randomized algorithm for higher order abstract Voronoi diagrams, Algorithmica, 81, 2317-2345, 2019 · Zbl 1421.68159 · doi:10.1007/s00453-018-00536-7 |
| [43] | Erdős, P.; Lovász, L.; Simmons, A.; Straus, EG; Srivastava, JN, Dissection graphs of planar point sets, A Survey of Combinatorial Theory, 139-149, 1973, Amsterdam: Elsevier, Amsterdam · Zbl 0258.05112 · doi:10.1016/B978-0-7204-2262-7.50018-1 |
| [44] | Dey, T., Improved bounds for planar k-sets and related problems, Discrete Comput. Geom., 19, 373-382, 1989 · Zbl 0899.68107 · doi:10.1007/PL00009354 |
| [45] | Roos, T., Voronoi diagrams over dynamic scenes, Discrete Appl. Math., 43, 243-259, 1993 · Zbl 0770.68115 · doi:10.1016/0166-218X(93)90115-5 |
| [46] | Guibas, L.; Stolfi, J.; Spehner, JC, Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams, ACM Trans. Graph, 4, 74-123, 1985 · Zbl 0586.68059 · doi:10.1145/282918.282923 |
| [47] | Alon, N.; Győri, E., The number of small semi-spaces of a finite set of points in the plane, J. Combin. Theory Ser. A., 41, 154-157, 1986 · Zbl 0584.05003 · doi:10.1016/0097-3165(86)90122-6 |
| [48] | Dobrin, A., A review of properties and variations of Voronoi diagrams, Whitman Coll., 10, 1453, 1-43, 2005 |
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.
