×

Efficiently approximating color-spanning balls. (English) Zbl 1339.68272

Summary: Suppose \(n\) colored points with \(k\) colors in \(\mathbb{R}^d\) are given. The Smallest Color-Spanning Ball (SCSB) is the smallest ball containing at least one point of each color. As the computation of the SCSB in \(L_p\) metric (\(p \geq 1\)) is time-consuming, we focus on approximately computing the SCSB in near-linear time. Initially, we propose a 3-approximation algorithm running in \(O(n \log n)\) time. This algorithm is then utilized to present a \((1 + \varepsilon)\)-approximation algorithm with the running time of \(O((\frac{1}{\varepsilon})^d n \log n)\). We improve the running time to \(O((\frac{1}{\varepsilon})^d n)\) using randomized techniques. Afterward, spanning colors with two balls is studied. For a special case where \(d = 1\), there is an algorithm with \(O(n^2)\) time. We demonstrate that for any \(\varepsilon > 0\) under the assumption that SETH is true, no approximation algorithm running in \(O(n^{2 - \varepsilon})\) time exists for the problem even in one-dimensional space. Nevertheless, we consider the \(L_\infty\) metric where a ball is an axis-parallel hypercube and present a \((1 + \varepsilon)\)-approximation algorithm running in \(O((\frac{1}{\varepsilon})^{2d}(\frac{n^2}{k})\log^2 n)\) time which is remarkable when \(k\) is large. This time can be reduced to \(O((\frac{1}{\varepsilon})\frac{n^2}{k}\log n)\) when \(d = 1\).

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68Q25 Analysis of algorithms and problem complexity
68W20 Randomized algorithms
68W25 Approximation algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abellanas, Manuel; Hurtado, Ferran; Icking, Christian; Klein, Rolf; Langetepe, Elmar; Ma, Lihong; Palop, Belén; Sacristán, Vera, Smallest Color-Spanning Objects (2001), Springer · Zbl 1006.68559
[2] Arya, Sunil; Mount, David M.; Netanyahu, Nathan S.; Silverman, Ruth; Wu, Angela Y., An optimal algorithm for approximate nearest neighbor searching fixed dimensions, J. ACM, 45, 6, 891-923 (1998) · Zbl 1065.68650
[3] Chan, Timothy M., Faster core-set constructions and data stream algorithms in fixed dimensions, (Proceedings of the Twentieth Annual Symposium on Computational Geometry (2004), ACM), 152-159 · Zbl 1377.68322
[4] Drezner, Zvi, On the rectangular p-center problem, Naval Res. Logist., 34, 2, 229-234 (1987) · Zbl 0614.90034
[5] Eppstein, David, Faster construction of planar two-centers, (SODA, vol. 97 (1997)), 131-138 · Zbl 1321.68500
[6] Frederickson, Greg N.; Johnson, Donald B., Generalized selection and ranking: sorted matrices, SIAM J. Comput., 13, 1, 14-30 (1984) · Zbl 0537.68059
[7] Gupta, Prosenjit; Janardan, Ravi; Smid, Michiel, Further results on generalized intersection searching problems: counting, reporting, and dynamization, J. Algorithms, 19, 2, 282-317 (1995) · Zbl 0839.68106
[8] Huttenlocher, Daniel P.; Kedem, Klara; Sharir, Micha, The upper envelope of Voronoi surfaces and its applications, Discrete Comput. Geom., 9, 1, 267-291 (1993) · Zbl 0770.68111
[9] Impagliazzo, Russell; Paturi, Ramamohan, Complexity of k-sat, (Proceedings of the Fourteenth Annual IEEE Conference on Computational Complexity. Proceedings of the Fourteenth Annual IEEE Conference on Computational Complexity, 1999 (1999), IEEE), 237-240 · Zbl 0990.68079
[10] Impagliazzo, Russell; Paturi, Ramamohan; Zane, Francis, Which problems have strongly exponential complexity?, (Proceedings of the 39th Annual Symposium on Foundations of Computer Science. Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998 (1998), IEEE), 653-662 · Zbl 1006.68052
[11] Jiang, Minghui; Wang, Haitao, Shortest color-spanning intervals, Theoret. Comput. Sci., 609, 561-568 (2016) · Zbl 1333.68257
[12] Khanteimouri, Payam; Mohades, Ali; Abam, Mohammad Ali; Kazemi, Mohammad Reza, Computing the smallest color-spanning axis-parallel square, (Algorithms and Computation (2013), Springer), 634-643 · Zbl 1406.68120
[13] Khanteimouri, Payam; Mohades, Ali; Abam, Mohammad Ali; Kazemi, Mohammad Reza, Spanning colored points with intervals, (CCCG (2013)) · Zbl 1406.68120
[14] Khuller, Samir; Matias, Yossi, A simple randomized sieve algorithm for the closest-pair problem, Inform. and Comput., 118, 1, 34-37 (1995) · Zbl 0827.68113
[15] Löffler, Maarten, Data imprecision in computational geometry (2009), Utrecht University, PhD thesis
[16] Lokshtanov, Daniel; Marx, Dániel; Saurabh, Saket, Lower bounds based on the exponential time hypothesis, Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, 105, 41-72 (2011) · Zbl 1258.68068
[17] Matoušek, Jiří, On enclosing k points by a circle, Inform. Process. Lett., 53, 4, 217-221 (1995) · Zbl 0875.68895
[18] Patrascu, Mihai; Williams, Ryan, On the possibility of faster sat algorithms, (SODA, vol. 10 (2010), SIAM), 1065-1075 · Zbl 1288.68135
[19] Sharir, Micha, A near-linear algorithm for the planar 2-center problem, Discrete Comput. Geom., 18, 2, 125-134 (1997) · Zbl 0878.68131
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.