Online unit clustering in higher dimensions

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 mathbbZd, d∈ mathbbN, 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.