Journal Article
@Article
Artikel in Fachzeitschrift

Show entries of:

this year (2023) | last year (2022) | two years ago (2021) | Notes URL

Action:

login to update
Options:








Author, Editor(s)
Author(s):
Teramoto, Sachio
Asano, Tetsuo
Katoh, Naoki
Doerr, Benjamin		dblp
dblp
dblp
dblp
Not MPG Author(s):
Teramoto, Sachio
Asano, Tetsuo
Katoh, Naoki

BibTeX cite key*:

inserpoints2006

Title

Title*:

Inserting Points Uniformly at Every Instance

Journal

Journal Title*:

IEICE - Transactions on Information and Systems
Journal's URL:


Download URL
for the article:

http://ietisy.oxfordjournals.org/cgi/reprint/E89-D/8/2348
Language:

English

Publisher

Publisher's
Name:

Oxford University Press
Publisher's URL:


Publisher's
Address:

Oxford, UK
ISSN:

0916-8532

Vol, No, pp, Date

Volume*:

E89-D
Number:

8

Publishing Date:

2006

Pages*:

2348-2356
Number of
VG Pages:

15

Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) 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{lfloor}n/2{rfloor}/({lfloor}n/2{rfloor}+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.

URL for the Abstract:

http://portal.acm.org/citation.cfm?id=1184861.1185096&coll=GUIDE&dl=%23url.coll
http://ietisy.oxfordjournals.org/cgi/content/abstract/E89-D/8/2348

Categories,
Keywords:


HyperLinks / References / URLs:

http://dx.doi.org/10.1093/ietisy/e89-d.8.2348

Copyright Message:


Personal Comments:


Download
Access Level:

Intranet

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{inserpoints2006,
AUTHOR = {Teramoto, Sachio and Asano, Tetsuo and Katoh, Naoki and Doerr, Benjamin},
 TITLE = {Inserting Points Uniformly at Every Instance},
 JOURNAL = {IEICE - Transactions on Information and Systems},
 PUBLISHER = {Oxford University Press},
 YEAR = {2006},
 NUMBER = {8},
 VOLUME = {E89-D},
 PAGES = {2348--2356},
 ADDRESS = {Oxford, UK},
 ISBN = {0916-8532},
}

Entry last modified by Christine Kiesel, 02/07/2007
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Mathias Bader		Created
01/02/2007 16:45:04
Revisions
3.
2.
1.
0.
Editor(s)
Christine Kiesel
Christine Kiesel
Mathias Bader
Mathias Bader
Edit Dates
07.02.2007 10:14:56
07.02.2007 10:09:55
02.01.2007 16:46:56
02.01.2007 16:45:04