Efficiently approximating color-spanning balls

Suppose n colored points with k   colors in RdRd 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 LpLp metric (p≥1p≥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(nlog⁡n)O(nlog⁡n) time. This algorithm is then utilized to present a (1+ε)(1+ε)-approximation algorithm with the running time of O((1ε)dnlog⁡n). We improve the running time to O((1ε)dn) using randomized techniques. Afterward, spanning colors with two balls is studied. For a special case where d=1d=1, there is an algorithm with O(n2)O(n2) time. We demonstrate that for any ε>0ε>0 under the assumption that SETH is true, no approximation algorithm running in O(n2−ε)O(n2−ε) time exists for the problem even in one-dimensional space. Nevertheless, we consider the L∞L∞ metric where a ball is an axis-parallel hypercube and present a (1+ε)(1+ε)-approximation algorithm running in O((1ε)2d(n2k)log2⁡n) time which is remarkable when k   is large. This time can be reduced to O((1ε)n2klog⁡n) when d=1d=1.