Parity-Constrained Triangulations with Steiner Points

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