# Item

ITEM ACTIONSEXPORT

Released

Journal Article

#### Inserting Points Uniformly at Every Instance

##### MPS-Authors

##### Locator

There are no locators available

##### Fulltext (public)

There are no public fulltexts available

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Teramoto, S., Asano, T., Katoh, N., & Doerr, B. (2006). Inserting Points Uniformly
at Every Instance.* IEICE - Transactions on Information and Systems,* *E89-D*,
2348-2356.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-2338-5

##### 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 2n/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.