Inserting Points Uniformly at Every Instance

Sachio TERAMOTO  Tetsuo ASANO  Naoki KATOH  Benjamin DOERR  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E89-D   No.8   pp.2348-2356
Publication Date: 2006/08/01
Online ISSN: 1745-1361
DOI: 10.1093/ietisy/e89-d.8.2348
Print ISSN: 0916-8532
Type of Manuscript: INVITED PAPER (Special Section on Invited Papers from New Horizons in Computing)
Category: 
Keyword: 
algorithm,  circle packing,  computational geometry,  discrepancy,  local search,  uniformity,  

Full Text: PDF(454.1KB)
>>Buy this Article


Summary: 
Arranging n points as uniformly as possible is a frequently occurring problem. It is equivalent to packing n equal and non-overlapping circles in a unit square. In this paper we generalize this problem in such a way that points are inserted one by one with uniformity preserved at every instance. Our criterion for uniformity is to minimize the gap ratio (which is the maximum gap over the minimum gap) at every point insertion. We present a linear time algorithm for finding an optimal n-point sequence with the maximum gap ratio bounded by in the 1-dimensional case. We describe how hard the same problem is for a point set in the plane and propose a local search heuristics for finding a good solution.