On some geometric problems of color-spanning sets. (English) Zbl 1275.90080

Summary: We study several geometric problems of color-spanning sets: given \(n\) points with \(m\) colors in the plane, selecting \(m\) points with \(m\) distinct colors such that some geometric properties of the \(m\) selected points are minimized or maximized. The geometric properties are the maximum diameter, the largest closest pair, the planar smallest minimum spanning tree, the planar largest minimum spanning tree and the planar smallest perimeter convex hull. We propose an \(O(n ^{1+\varepsilon })\) time algorithm for the maximum diameter color-spanning set problem where \(\varepsilon \) could be an arbitrarily small positive constant. Then, we present hardness proofs for the other problems and propose two efficient constant factor approximation algorithms for the planar smallest perimeter color-spanning convex hull problem.


90C27 Combinatorial optimization
90C60 Abstract computational complexity for mathematical programming problems
Full Text: DOI


[1] Abellanas, M.; Hurtado, F.; Icking, C.; Klein, R.; Langetepe, E.; Ma, L.; Palop, B.; Sacristan, V., The farthest color Voronoi diagram and related problems, 113-116 (2001)
[2] Abellanas, M.; Hurtado, F.; Icking, C.; Klein, R.; Langetepe, E.; Ma, L.; Palop, B.; Sacristan, V., Smallest color-spanning objects, 278-289 (2001) · Zbl 1006.68559
[3] Agarwal, PK; Eppstein, D.; Matousek, J., Dynamic half-space reporting, geometric optimization, and minimum spanning trees, 80-89 (1992) · Zbl 0977.68567 · doi:10.1109/SFCS.1992.267816
[4] Beresford AR, Stajano F (2003) Location privacy in pervasive computing. IEEE Pervasive Comput 2(1):46-55 · doi:10.1109/MPRV.2003.1186725
[5] Berg M, Cheong O, Kreveld M, Overmars M (2008) Computational geometry: algorithms and applications, 3rd edn. Springer, Berlin · Zbl 1140.68069
[6] Boissonnat, JD; Lazard, S., Convex hulls of bounded curvature, 14-19 (1996)
[7] Cheema MA, Lin X, Wang W, Zhang W, Pei J (2010) Probabilistic reverse nearest neighbor queries on uncertain data. IEEE Trans Knowl Data Eng 22(4):550-564 · doi:10.1109/TKDE.2009.108
[8] Cheng R, Kalashnikov DV, Prabhakar S (2004) Querying imprecise data in moving object environments, knowledge and data engineering. IEEE Trans Knowl Data Eng 16(9):1112-1127 · doi:10.1109/TKDE.2004.46
[9] Cheng, R.; Zhang, Y.; Bertino, E.; Prabhakar, S., Preserving user location privacy in mobile data management infrastructures, No. 4258, 393-412 (2006), Berlin · doi:10.1007/11957454_23
[10] Das S, Goswani PP, Nandy SC (2009) Smallest color-spanning object revised. Int J Comput Geom Appl 19(5):457-478 · Zbl 1178.65020 · doi:10.1142/S0218195909003076
[11] Eppstein D (1996) Average case analysis of dynamic geometric optimization. Comput Geom Theory Appl 6(1):45-68 · Zbl 0849.68121 · doi:10.1016/0925-7721(95)00018-6
[12] Fleischer, R.; Xu, X., Computing minimum diameter color-spanning sets, No. 6213, 285-292 (2010), Berlin · Zbl 1288.68115 · doi:10.1007/978-3-642-14553-7_27
[13] Gedik, B.; Liu, L., A customizable k-anonymity model for protecting location privacy, 620-629 (2005)
[14] Graham RL (1972) An efficient algorithm for determining the convex hull of a finite planar set. Inf Process Lett 26:132-133 · Zbl 0236.68013 · doi:10.1016/0020-0190(72)90045-2
[15] Khanban, AA; Edalat, A., Computing Delaunay triangulation with imprecise input data, 94-97 (2003)
[16] Kreveld, MV; Löffler, M., Largest bounding box, smallest diameter, and related problems on imprecise points, No. 4619, 447-458 (2007), Berlin
[17] Nagai, T.; Tokura, N., Tight error bounds of geometric problems on convex objects with imprecise coordinates, No. 2098, 252-263 (2000), Berlin · Zbl 0998.52013 · doi:10.1007/3-540-47738-1_24
[18] Pei, J.; Jiang, B.; Lin, X.; Yuan, Y., Probabilistic skylines on uncertain data, 15-26 (2007)
[19] Pfoser, D.; Jensen, C., Capturing the uncertainty of moving-objects representations, No. 1651, 111-131 (1999), Berlin · doi:10.1007/3-540-48482-5_9
[20] Preparata FP, Shamos MI (1985) Computational geometry: an introduction. Springer, New York · Zbl 0759.68037 · doi:10.1007/978-1-4612-1098-6
[21] Sistla, PA; Wolfson, O.; Chamberlain, S.; Dao, S., Querying the uncertain position of moving objects, No. 1399, 310-337 (1997), Berlin · doi:10.1007/BFb0053708
[22] Yuen SM, Tao Y, Xiao X, Pei J, Zhang D (2010) Superseding nearest neighbor search on uncertain spatial databases. IEEE Trans Knowl Data Eng 22(7):1041-1055 · doi:10.1109/TKDE.2009.137
[23] Zhang, D.; Chee, YM; Mondal, A.; Tung, AKH; Kitsuregawa, M., Keyword search in spatial databases: towards searching by document, 688-699 (2009) · doi:10.1109/ICDE.2009.77
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.