English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  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

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Kettner, Lutz1, Author           
Kirkpatrick, David, Author
Mantler, Andrea, Author
Snoeyink, Jack, Author
Speckmann, Bettina, Author
Takeuchi, Fumihiko, Author
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 Abstract: 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

show
hide
Language(s): eng - English
 Dates: 2004-06-152003
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: Peer
 Identifiers: eDoc: 202038
Other: Local-ID: C1256428004B93B8-A20C349D3E243F5FC1256D0A005B3F31-Kettner2003DegreeBound
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Computational Geometry - Theory and Applications
Source Genre: Journal
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 25 Sequence Number: - Start / End Page: 3 - 12 Identifier: ISSN: 0925-7721