English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Journal Article

Tight Degree Bounds for Pseudo-triangulations of Points

MPS-Authors
/persons/resource/persons44766

Kettner,  Lutz
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Ressource
No external resources are shared
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available
Citation

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.


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-2E64-F
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.