Online unit covering in Euclidean space

We revisit the online Unit Covering problem in higher dimensions: Given a set of n points in R d, that arrive one by one, cover the points by balls of unit radius, so as to minimize the number of balls used. In this paper, we work in R d using the Euclidean distance. (I) We give an online deterministic algorithm with competitive ratio O ( 1. 321 d ), thereby improving on the previous record, O ( 2 d d log ⁡ d ), due to Charikar et al. (2004), by an exponential factor. In particular, the competitive ratios are 5 in the plane and 12 in 3-space (the previous ratios were 7 and 21, respectively). For d = 3, the ratio of our online algorithm matches the ratio of the current best offline algorithm for the same problem due to Biniaz et al. (2017), which is remarkable (and rather unusual). (II) We show that the competitive ratio of every deterministic online algorithm for Unit Covering in R d under the L 2 norm is at least d + 1 for every d ≥ 1. This greatly improves upon the previous best lower bound, Ω ( log ⁡ d / log ⁡ log ⁡ log ⁡ d ), due to Charikar et al. (2004). (III) We generalize the above result to Unit Covering in R d under the L C norm, where C is a centrally symmetric convex body, via the illumination number. (IV) We obtain lower bounds of 4 and 5 for the competitive ratio of any deterministic algorithm for online Unit Covering in R 2 and R 3, respectively; the previous best lower bounds were 3 for both cases. (V) When the input points are from the square or hexagonal lattice in R 2, we give deterministic online algorithms for Unit Covering with an optimal competitive ratio of 3. For the cubic lattice in R 3, we give a deterministic online algorithm with a competitive ratio of 5.

Authors

• Adrian Dumitrescu
• Anirban Ghosh
• Csaba D. Tóth

Keywords

• Online algorithm
• Unit covering
• Unit clustering
• Competitive ratio
• Illumination number
• Newton number