Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

 
 
DownloadE-Mail
  Inserting Points Uniformly at Every Instance

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.

Item is

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Teramoto, Sachio, Autor
Asano, Tetsuo1, Autor           
Katoh, Naoki, Autor
Doerr, Benjamin1, Autor           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: 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.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2007-02-102006
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: Expertenbegutachtung
 Identifikatoren: eDoc: 314534
Anderer: Local-ID: C1256428004B93B8-AA6C18ED7CFD2C64C125725700568662-inserpoints2006
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: IEICE - Transactions on Information and Systems
Genre der Quelle: Zeitschrift
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: E89-D Artikelnummer: - Start- / Endseite: 2348 - 2356 Identifikator: ISSN: 0916-8532