×

Diverse partitions of colored points. (English) Zbl 07498709

Lubiw, Anna (ed.) et al., Algorithms and data structures. 17th international symposium, WADS 2021, virtual event, August 9–11, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12808, 641-654 (2021).
Summary: Imagine that a set of objects is represented by points in space and that different types or classes of objects are represented by colors. We study the algorithmic problem of creating convex or Voronoi partitions of space with maximally diverse cells, using two classic diversity measures: the richness (number of different colors) and the Shannon index. The diversity of a partition is the sum of the diversity scores of its cells. Hence, we wish to compute either a diverse convex partition (DCP) or a diverse Voronoi partition (DVP), which maximizes the diversity score of the partition. Surprisingly, computing a DVP is NP-hard already in 1D and for only four colors, while DCP can easily be computed with dynamic programming. We show that DVP can be solved in polynomial time in 1D if a discrete set of candidate positions for the Voronoi sites is part of the input. These results apply to both the richness and the Shannon index. For richness, we also present a polynomial-time algorithm to compute a Voronoi partition whose diversity is at least \(1-\varepsilon\) times the optimal diversity. In 2D, we show that both DCP and DVP are NP-hard, for richness as diversity measure. The reductions use constantly many colors for DVP and polynomially many colors for DCP.
For the entire collection see [Zbl 1482.68032].

MSC:

68P05 Data structures
68Wxx Algorithms in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bereg, S.; Bose, P.; Kirkpatrick, D., Equitable subdivisions within polygonal regions, Comput. Geom., 34, 1, 20-27 (2006) · Zbl 1098.65023 · doi:10.1016/j.comgeo.2005.06.003
[2] Bereg, S.; Díaz-Báñez, JM; Lara, D.; Pérez-Lantero, P.; Seara, C.; Urrutia, J., On the coarseness of bicolored point sets, Comput. Geom., 46, 1, 65-77 (2013) · Zbl 1251.05026 · doi:10.1016/j.comgeo.2012.04.003
[3] Bereg, S., Balanced partitions of 3-colored geometric sets in the plane, Discret. Appl. Math., 181, 21-32 (2015) · Zbl 1304.05008 · doi:10.1016/j.dam.2014.10.015
[4] Bespamyatnikh, S.; Kirkpatrick, D.; Snoeyink, J., Generalizing ham sandwich cuts to equitable subdivisions, Discret. Comput. Geom., 24, 4, 605-622 (2000) · Zbl 0966.68156 · doi:10.1007/s4540010065
[5] Blagojević, PV; Rote, G.; Steinmeyer, JK; Ziegler, GM, Convex equipartitions of colored point sets, Discret. Comput. Geom., 61, 2, 355-363 (2019) · Zbl 1407.52031 · doi:10.1007/s00454-017-9959-7
[6] Borodin, A.; Jain, A.; Lee, HC; Ye, Y., Max-sum diversification, monotone submodular functions, and dynamic updates, ACM Trans. Algorithms (TALG), 13, 3, 1-25 (2017) · Zbl 1452.68273 · doi:10.1145/3086464
[7] Chierichetti, F., Kumar, R., Lattanzi, S., Vassilvitskii, S.: Fair clustering through fairlets. In: Advances in Neural Information Processing Systems, pp. 5029-5037 (2017)
[8] Drosou, M.; Jagadish, H.; Pitoura, E.; Stoyanovich, J., Diversity in big data: a review, Big Data, 5, 2, 73-84 (2017) · doi:10.1089/big.2016.0054
[9] Dumitrescu, A.; Pach, J., Partitioning colored point sets into monochromatic parts, Int. J. Comput. Geom. Appl., 12, 5, 401-412 (2002) · Zbl 1152.68666 · doi:10.1142/S0218195902000943
[10] Farahani, RZ; SteadieSeifi, M.; Asgari, N., Multiple criteria facility location problems: a survey, Appl. Math. Model., 34, 7, 1689-1709 (2010) · Zbl 1193.90143 · doi:10.1016/j.apm.2009.10.005
[11] Hartvigsen, D., Recognizing Voronoi diagrams with linear programming, ORSA J. Comput., 4, 4, 369-374 (1992) · Zbl 0758.68056 · doi:10.1287/ijoc.4.4.369
[12] Holmsen, AF; Kynčl, J.; Valculescu, C., Near equipartitions of colored point sets, Comput. Geom., 65, 35-42 (2017) · Zbl 1377.65026 · doi:10.1016/j.comgeo.2017.05.001
[13] Kaneko, A., Kano, M.: Discrete geometry on red and blue points in the plane, a survey. In: Aronov, B., Basu, S., Pach, J., Sharir, M. (eds.) Discrete and Computational Geometry, The Goodman-Pollack Festschrift, pp. 551-570. Springer, Heidelberg (2003). doi:10.1007/978-3-642-55566-4_25 · Zbl 1079.52505
[14] Lacevic, B., Amaldi, E.: On population diversity measures in Euclidean space. In: IEEE Congress on Evolutionary Computation, pp. 1-8 (2010) · Zbl 1215.62004
[15] Magurran, AE, Ecological Diversity and its Measurement (1988), Princeton: Princeton University Press, Princeton · doi:10.1007/978-94-015-7358-0
[16] Majumder, S.; Nandy, SC; Bhattacharya, BB, Separating multi-color points on a plane with fewest axis-parallel lines, Fundamenta Informaticae, 99, 3, 315-324 (2010) · Zbl 1204.68245 · doi:10.3233/FI-2010-251
[17] Tang, EK; Suganthan, PN; Yao, X., An analysis of diversity measures, Mach. Learn., 65, 1, 247-271 (2006) · Zbl 1470.68188 · doi:10.1007/s10994-006-9449-2
[18] Tuomisto, H., A diversity of beta diversities: straightening up a concept gone awry. Part 1. Defining beta diversity as a function of alpha and gamma diversity, Ecography, 33, 1, 2-22 (2010) · doi:10.1111/j.1600-0587.2009.05880.x
[19] Whittaker, RH, Vegetation of the Siskiyou mountains, Oregon and California, Ecol. Monogr., 30, 3, 279-338 (1960) · doi:10.2307/1943563
[20] Zheng, K.; Wang, H.; Qi, Z.; Li, J.; Gao, H., A survey of query result diversification, Knowl. Inf. Syst., 51, 1, 1-36 (2016) · doi:10.1007/s10115-016-0990-4
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.