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

Atallah, Mikhail (ed.) et al., Frontiers in algorithmics and algorithmic aspects in information and management. Joint international conference, FAW-AAIM 2011, Jinhua, China, May 28–31, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-21203-1/pbk). Lecture Notes in Computer Science 6681, 113-124 (2011).
Summary: In this paper we study several geometric problems of color-spanning sets: given \(N\) points with \(M\) colors in the plane, choosing \(M\) points with distinct colors such that some geometric properties of those \(M\) points are minimized or maximized. The geometric properties studied in this paper are the maximum diameter, the largest closest pair, and the minimum planar spanning tree. We give an \(O(N \log N)\) expected time algorithm for the maximum diameter problem. For the largest closest pair and the minimum planar spanning tree problems, we give hardness proofs.
For the entire collection see [Zbl 1214.68006].


68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W05 Nonnumerical algorithms
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. In: Proceedings of the 17th European Workshop on Computational Geometry (EWCG 2001), pp. 113-116 (2001)
[2] Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation. Springer, Germany (1999) · Zbl 0937.68002 · doi:10.1007/978-3-642-58412-1
[3] Beresford, A.R., Stajano, F.: Location privacy in pervasive computing. IEEE Pervasive Computing 2(1), 46–55 (2003) · doi:10.1109/MPRV.2003.1186725
[4] Berg, M., Cheong, O., Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer, Heidelberg (2008) · Zbl 1140.68069 · doi:10.1007/978-3-540-77974-2
[5] Cheng, R., Kalashnikov, D.V., Prabhakar, S.: Querying imprecise data in moving object environments, knowledge and data engineering. IEEE Transactions on Knowledge and Data Engineering 16(9), 1112–1127 (2004) · doi:10.1109/TKDE.2004.46
[6] Cheng, R., Zhang, Y., Bertino, E., Prabhakar, S.: Preserving user location privacy in mobile data management infrastructures. In: Danezis, G., Golle, P. (eds.) PET 2006. LNCS, vol. 4258, pp. 393–412. Springer, Heidelberg (2006) · doi:10.1007/11957454_23
[7] Das, S., Goswani, P.P., Nandy, S.C.: Smallest color-spanning object revised. International Journal of Computational Geometry and Applications 19(5), 457–478 (2009) · Zbl 1178.65020 · doi:10.1142/S0218195909003076
[8] Fleischer, R., Xu, X.: Computing minimum diameter color-spanning sets. In: Lee, D.-T., Chen, D.Z., Ying, S. (eds.) FAW 2010. LNCS, vol. 6213, pp. 285–292. Springer, Heidelberg (2010) · Zbl 1288.68115 · doi:10.1007/978-3-642-14553-7_27
[9] Gedik, B., Liu, L.: A customizable k-anonymity model for protecting location privacy. In: Proceedings of the 25th International Conference on Distributed Computing Systems (ICDCS 2005), pp. 620–629 (2005)
[10] Pfoser, D., Jensen, C.S.: Capturing the uncertainty of moving-object representations. In: Güting, R.H., Papadias, D., Lochovsky, F.H. (eds.) SSD 1999. LNCS, vol. 1651, pp. 111–131. Springer, Heidelberg (1999) · doi:10.1007/3-540-48482-5_9
[11] Preparata, F.P., Shamos, M.I.: Computational geometry: an introduction. Springer-Verlag New York, Inc., New York (1985) · Zbl 0575.68059 · doi:10.1007/978-1-4612-1098-6
[12] Sistla, P.A., Wolfson, O., Chamberlain, S., Dao, S.: Querying the uncertain position of moving objects. In: Etzion, O., Jajodia, S., Sripada, S. (eds.)Temporal Databases: Research and Practice. LNCS, vol. 1399, pp. 310–337. Springer, Heidelberg (1998) · doi:10.1007/BFb0053708
[13] Zhang, D., Chee, Y.M., Mondal, A., Tung, A.K.H., Kitsuregawa, M.: Keyword search in spatial databases: Towards searching by document. In: Proceedings of the 25th IEEE International Conference on Data Engineering (ICDE 2009), pp. 688–699 (2009) · doi:10.1109/ICDE.2009.77
[14] Eppstein, D.: Average case analysis of dynamic geometric optimization. Comput. Geom. Theory Appl. 6(1), 45–68 (1996) · Zbl 0849.68121 · doi:10.1016/0925-7721(95)00018-6
[15] Pei, J., Jiang, B., Lin, X., Yuan, Y.: Probabilistic Skylines on Uncertain Data. In: VLDB 2007, pp. 15–26 (2007)
[16] Cheema, M.A., Lin, X., Wang, W., Zhang, W., Pei, J.: Probabilistic Reverse Nearest Neighbor Queries on Uncertain Data. IEEE Trans. Knowl. Data Eng. 22(4), 550–564 (2010) · doi:10.1109/TKDE.2009.108
[17] Yuen, S.M., Tao, Y., Xiao, X., Pei, J., Zhang, D.: Superseding Nearest Neighbor Search on Uncertain Spatial Databases. IEEE Trans. Knowl. Data Eng. 22(7), 1041–1055 (2010) · doi:10.1109/TKDE.2009.137
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.