2013/04/22 by Sándor P. Fekete, Fekete, Sándor P., Nils Schweer +3
Computer Science · Engineering · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #Optimization and Packing Problems #Optimization and Search Problems #cs.CG #cs.DS
paper · pdf · doi:10.48550/arxiv.1304.5971
15 pages, 9 figures, 3 tables; extended abstract version appears in WALCOM 2013, LNCS 7748, pp. 41-52
arxiv created 2013/04/22 · openalex publication_date 2013/04/22 · arxiv updated 2013/04/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the following online allocation problem: Given a unit square S, and a sequence of numbers ni between 0 and 1, with partial sum bounded by 1; at each step i, select a region Ci of previously unassigned area ni 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. 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 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.