Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
Zur Ablage hinzufügen
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  Controlled Perturbation for Delaunay Triangulations

Funke, S., Klein, C., Mehlhorn, K., & Schmitt, S. (2005). Controlled Perturbation for Delaunay Triangulations. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 1047-1056). Philadelphia, PA: SIAM. Retrieved from http://dl.acm.org/citation.cfm?id=1070432.1070582.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-2622-0 Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-0024-AD20-0
Genre: Konferenzbeitrag
Latex : Controlled Perturbation for {Delaunay} Triangulations

Dateien

einblenden: Dateien
ausblenden: Dateien
:
CP-paper-FINAL.pdf (beliebiger Volltext), 219KB
 
Datei-Permalink:
-
Name:
CP-paper-FINAL.pdf
Beschreibung:
-
OA-Status:
Sichtbarkeit:
Privat
MIME-Typ / Prüfsumme:
application/pdf
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-
Lizenz:
-
:
184.pdf (beliebiger Volltext), 158KB
 
Datei-Permalink:
-
Name:
184.pdf
Beschreibung:
-
OA-Status:
Sichtbarkeit:
Privat
MIME-Typ / Prüfsumme:
application/pdf
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-
Lizenz:
-

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Funke, Stefan1, Autor           
Klein, Christian1, Autor           
Mehlhorn, Kurt1, Autor           
Schmitt, Susanne1, Autor           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: Most geometric algorithms are idealistic in the sense that they are designed for the Real-RAM model of computation and for inputs in general position. Real inputs may be degenerate and floating point arithmetic is only an approximation of real arithmetic. Perturbation replaces an input by a nearby input which is (hopefully) in general position and on which the algorithm can be run with floating point arithmetic. Controlled perturbation as proposed by Halperin et al. calls for more: control over the amount of perturbation needed for a given precision of the floating point system. Or conversely, a control over the precision needed for a given amount of perturbation. Halperin et al.~gave controlled perturbation schemes for arrangements of polyhedral surfaces, spheres, and circles. We extend their work and point out that controlled perturbation is a general scheme for converting idealistic algorithms into algorithms which can be executed with floating point arithmetic. We also show how to use controlled perturbation in the context of randomized geometric algorithms without deteriorating the running time. Finally, we give concrete schemes for planar Delaunay triangulations and convex hulls and Delaunay triangulations in arbitrary dimensions. We analyze the relation between the perturbation amount and the precision of the floating point system. We also report about experiments with a planar Delaunay diagram algorithm.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2006-06-1320052005
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 279162
Anderer: Local-ID: C1256428004B93B8-51E79341608E6746C1256FA2005B7772-FKMS2005
BibTex Citekey: FKMS2005
URI: http://dl.acm.org/citation.cfm?id=1070432.1070582
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms
Veranstaltungsort: Vancouver, Canada
Start-/Enddatum: 2005-01-23 - 2005-01-25

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms
  Kurztitel : SODA 2005
Genre der Quelle: Konferenzband
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: Philadelphia, PA : SIAM
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 1047 - 1056 Identifikator: ISBN: 0-89871-585-7