Parity-Constrained Triangulations with Steiner Points

Let P⊂R2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${P\subset\mathbb{R}^{2}}$$\end{document} be a set of n points, of which k lie in the interior of the convex hull CH(P) of P. Let us call a triangulation T of P even (odd) if and only if all its vertices have even (odd) degree, and pseudo-even (pseudo-odd) if at least the k interior vertices have even (odd) degree. On the one hand, triangulations having all its interior vertices of even degree have one nice property; their vertices can be 3-colored, see (Heawood in Quart J Pure Math 29:270–285, 1898, Steinberg in A source book for challenges and directions, vol 55. Elsevier, Amsterdam, pp 211–248, 1993, Diks et al. in Lecture notes in computer science, vol 2573. Springer, Berlin, pp 138–149, 2002). On the other hand, odd triangulations have recently found an application in the colored version of the classic “Happy Ending Problem” of Erdős and Szekeres, see (Aichholzer et al. in SIAM J Discrete Math 23(4):2147–2155, 2010). It is easy to prove that there are sets of points that admit neither pseudo-even nor pseudo-odd triangulations. In this paper we show nonetheless how to construct a set of Steiner points S = S(P) of size at most k3+c\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\frac{k}{3} + c}$$\end{document} , where c is a positive constant, such that a pseudo-even (pseudo-odd) triangulation can be constructed on P∪S\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${P \cup S}$$\end{document} . Moreover, we also show that even (odd) triangulations can always be constructed using at most n3+c\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\frac{n}{3} + c}$$\end{document} Steiner points, where again c is a positive constant. Our constructions have the property that all but at most two Steiner points lie in the interior of CH(P).