Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

 
 
DownloadE-Mail
  Tight Degree Bounds for Pseudo-triangulations of Points

Kettner, L., Kirkpatrick, D., Mantler, A., Snoeyink, J., Speckmann, B., & Takeuchi, F. (2003). Tight Degree Bounds for Pseudo-triangulations of Points. Computational Geometry - Theory and Applications, 25, 3-12.

Item is

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Kettner, Lutz1, Autor           
Kirkpatrick, David, Autor
Mantler, Andrea, Autor
Snoeyink, Jack, Autor
Speckmann, Bettina, Autor
Takeuchi, Fumihiko, Autor
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: We show that every set of $n$ points in general position has a minimum pseudo-triangulation whose maximum vertex degree is five. In addition, we demonstrate that every point set in general position has a minimum pseudo-triangulation whose maximum face degree is four (i.e.\ each interior face of this pseudo-triangulation has at most four vertices). Both degree bounds are tight. Minimum pseudo-triangulations realizing these bounds (individually but not jointly) can be constructed in $O(n \log n)$ time.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2004-06-152003
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: Expertenbegutachtung
 Identifikatoren: eDoc: 202038
Anderer: Local-ID: C1256428004B93B8-A20C349D3E243F5FC1256D0A005B3F31-Kettner2003DegreeBound
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Computational Geometry - Theory and Applications
Genre der Quelle: Zeitschrift
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 25 Artikelnummer: - Start- / Endseite: 3 - 12 Identifikator: ISSN: 0925-7721