Degree Bounds for Constrained Pseudo-Triangulations

O. Aichholzer, M. Hoffmann, B. Speckmann, and C. D. Tóth

Abstract:

We introduce the concept of a constrained pointed pseudo-triangulation $\mathcal{T}_G$ of a point set $S$ with respect to a pointed planar straight line graph $G = (S, E)$. For the case that $G$ forms a simple polygon $P$ with vertex set $S$ we give tight bounds on the vertex degree of $\mathcal{T}_G$.



Reference: O. Aichholzer, M. Hoffmann, B. Speckmann, and C. D. Tóth. Degree bounds for constrained pseudo-triangulations. In Proc. $15th$ Annual Canadian Conference on Computational Geometry CCCG 2003, pages 155-158, Halifax, Nova Scotia, Canada, 2003.

www-data, 2020-09-10