Name
Abstract | ||
|---|---|---|
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 2⌊n/2⌋/(⌊n/2⌋+1) 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. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1093/ietisy/e89-d.8.2348 | IEICE Transactions |
Keywords | Field | DocType |
1-dimensional case,local search heuristics,linear time algorithm,good solution,point insertion,n point,maximum gap,inserting points uniformly,gap ratio,minimum gap,maximum gap ratio,local search,computational geometry,algorithm,circle packing,1 dimensional | Combinatorics,Computational geometry,Heuristics,Point set,Unit square,Local search (optimization),Circle packing,Time complexity,Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
E89-D | 8 | 1745-1361 |
Citations | PageRank | References |
9 | 1.35 | 11 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sachio Teramoto | 1 | 33 | 3.30 |
| Tetsuo Asano | 2 | 1448 | 229.35 |
| naoki katoh | 3 | 1101 | 187.43 |
| Benjamin Doerr | 4 | 1504 | 127.25 |