2017/08/08 by Adrian Dumitrescu, Csaba D. Tóth, Dumitrescu, Adrian +1 · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #F.2.2 #FOS: Computer and information sciences #H.3.3 #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1708.02662
openalex publication_date 2017/08/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We revisit the online Unit Clustering and Unit Covering problems in higher dimensions: Given a set of n points in a metric space, that arrive one by one, Unit Clustering asks to partition the points into the minimum number of clusters (subsets) of diameter at most one; while Unit Covering asks to cover all points by the minimum number of balls of unit radius. In this paper, we work in ℝd using the L_∞ norm. We show that the competitive ratio of any online algorithm (deterministic or randomized) for Unit Clustering must depend on the dimension d. We also give a randomized online algorithm with competitive ratio O(d2) for Unit Clustering of integer points (i.e., points in ℤd, d∈ ℕ, under L∞ norm). We show that the competitive ratio of any deterministic online algorithm for Unit Covering is at least 2d. This ratio is the best possible, as it can be attained by a simple deterministic algorithm that assigns points to a predefined set of unit cubes. We complement these results with some additional lower bounds for related problems in higher dimensions.