Tight Degree Bounds for Pseudo-triangulations of Points

Kettner, Lutz; Kirkpatrick, David; Mantler, Andrea; Snoeyink, Jack; Speckmann, Bettina; Takeuchi, Fumihiko

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

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 Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

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: https://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.