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 ni?[0,1] n i ? [ 0 , 1 ] with ? j = 0 i n j ? 1 ; at each step i , select a region Ci C i of previously unassigned area ni 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 Ci 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 ni n i has been studied. 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.
optimal shape of a city space-filling curves clustering average distance online problems competitive analysis