A Competitive Strategy for Distance-Aware Online Shape Allocation

We consider the following online allocation problem: Given a unit square S, and a sequence of numbers n i ∈ {0,1} with \(\sum_{j=0}^i n_j\leq 1\); at each step i, select a region C i of previously unassigned area n i in S. The objective is to make these regions compact in a distance-aware sense: minimize the maximum (normalized) average Manhattan distance between points from the same set C i . Related location problems have received a considerable amount of attention; in particular, the problem of determining the “optimal shape of a city”, i.e., allocating a single n i has been studied, both in a continuous and a discrete setting. We present an online strategy, based on an analysis of space-filling curves; for continuous shapes, we prove a factor of 1.8092, and 1.7848 for discrete point sets.