IEICE TRANSACTIONS on Information
Inserting Points Uniformly at Every Instance
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
- 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
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
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
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
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
ER -
English
