×

Computing minimum diameter color-spanning sets is hard. (English) Zbl 1260.68153

Summary: We show that the minimum diameter color-spanning set problem is NP-hard for \(L_p\) metric, \(1<p<\infty \).

MSC:

68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] M. Abellanas, F. Hurtado, C. Icking, R. Klein, E. Langetepe, L. Ma, B. Palop, V. Sacristan, The farthest color Voronoi diagram and related problems, in: Proceedings of the 17th European Workshop on Computational Geometry (EWCGʼ01), 2001, pp. 113-116.; M. Abellanas, F. Hurtado, C. Icking, R. Klein, E. Langetepe, L. Ma, B. Palop, V. Sacristan, The farthest color Voronoi diagram and related problems, in: Proceedings of the 17th European Workshop on Computational Geometry (EWCGʼ01), 2001, pp. 113-116. · Zbl 1006.68559
[2] Abellanas, M.; Hurtado, F.; Icking, C.; Klein, R.; Langetepe, E.; Ma, L.; Palop, B.; Sacristan, V., Smallest color-spanning objects, (Proceedings of the 9th European Symposium on Algorithms (ESAʼ01). Proceedings of the 9th European Symposium on Algorithms (ESAʼ01), Lecture Notes in Computer Science, vol. 2161 (2001), Springer), 278-289 · Zbl 1006.68559
[3] Y. Chen, S. Chen, Y. Gu, M. Hui, F. Li, C. Liu, L. Liu, B.C. Ooi, X. Yang, D. Zhang, Y. Zhou, MarcoPolo: A community system for sharing and integrating travel information on maps, in: Proceedings of the 12th International Conference on Extending Database Technology (EDBTʼ09), 2009, pp. 1148-1151.; Y. Chen, S. Chen, Y. Gu, M. Hui, F. Li, C. Liu, L. Liu, B.C. Ooi, X. Yang, D. Zhang, Y. Zhou, MarcoPolo: A community system for sharing and integrating travel information on maps, in: Proceedings of the 12th International Conference on Extending Database Technology (EDBTʼ09), 2009, pp. 1148-1151.
[4] Fan, C.; Ju, W.; Luo, J., On some geometric problems of color-spanning sets, (Proceedings of the 5th International Frontiers of Algorithmics Workshop (FAWʼ11). Proceedings of the 5th International Frontiers of Algorithmics Workshop (FAWʼ11), Lecture Notes in Computer Science, vol. 6681 (2011), Springer), 113-124 · Zbl 1329.68263
[5] Fleischer, R.; Xu, X., Computing minimum diameter color-spanning sets, (Proceedings of the 4th International Frontiers of Algorithmics Workshop (FAWʼ10). Proceedings of the 4th International Frontiers of Algorithmics Workshop (FAWʼ10), Lecture Notes in Computer Science, vol. 6213 (2010), Springer), 285-292 · Zbl 1288.68115
[6] D. Zhang, Y.M. Chee, A. Mondal, A.K.H. Tung, M. Kitsuregawa, Keyword search in spatial databases: Towards searching by document, in: Proceedings of the 25th IEEE International Conference on Data Engineering (ICDEʼ09), 2009, pp. 688-699.; D. Zhang, Y.M. Chee, A. Mondal, A.K.H. Tung, M. Kitsuregawa, Keyword search in spatial databases: Towards searching by document, in: Proceedings of the 25th IEEE International Conference on Data Engineering (ICDEʼ09), 2009, pp. 688-699.
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.