Inserting Points Uniformly at Every Instance

Sachio TERAMOTO; Tetsuo ASANO; Naoki KATOH; Benjamin DOERR

doi:10.1093/ietisy/e89-d.8.2348

Inserting Points Uniformly at Every Instance

Sachio TERAMOTO, Tetsuo ASANO, Naoki KATOH, Benjamin DOERR

Full Text Views

0

Cite this

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.

Publication: IEICE TRANSACTIONS on Information Vol.E89-D No.8 pp.2348-2356

Publication Date: 2006/08/01

Publicized

Online ISSN: 1745-1361

DOI: 10.1093/ietisy/e89-d.8.2348

Type of Manuscript: Special Section INVITED PAPER (Special Section on Invited Papers from New Horizons in Computing)

Category

Cite this

Copy

Sachio TERAMOTO, Tetsuo ASANO, Naoki KATOH, Benjamin DOERR, "Inserting Points Uniformly at Every Instance" in IEICE TRANSACTIONS on Information, vol. E89-D, no. 8, pp. 2348-2356, August 2006, doi: 10.1093/ietisy/e89-d.8.2348.
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 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.
URL: https://global.ieice.org/en_transactions/information/10.1093/ietisy/e89-d.8.2348/_p

Copy

@ARTICLE{e89-d_8_2348,
author={Sachio TERAMOTO, Tetsuo ASANO, Naoki KATOH, Benjamin DOERR, },
journal={IEICE TRANSACTIONS on Information},
title={Inserting Points Uniformly at Every Instance},
year={2006},
volume={E89-D},
number={8},
pages={2348-2356},
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 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.},
keywords={},
doi={10.1093/ietisy/e89-d.8.2348},
ISSN={1745-1361},
month={August},}

Copy

TY - JOUR
TI - Inserting Points Uniformly at Every Instance
T2 - IEICE TRANSACTIONS on Information
SP - 2348
EP - 2356
AU - Sachio TERAMOTO
AU - Tetsuo ASANO
AU - Naoki KATOH
AU - Benjamin DOERR
PY - 2006
DO - 10.1093/ietisy/e89-d.8.2348
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E89-D
IS - 8
JA - IEICE TRANSACTIONS on Information
Y1 - August 2006
AB - 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.
ER -