Parity-Constrained Triangulations with Steiner Points
Parity-Constrained Triangulations with Steiner Points
复制标题
具有 Steiner 点的奇偶约束三角剖分
DOI：
10.1007/s00373-013-1389-6
复制
发表时间：
2015
影响因子：
0.7
通讯作者：
V. Álvarez
中科院分区：
文献类型：
--
作者：
V. Álvarez
令 $${P\subset\mathbb{R}^{2}}$$P⊂R2 为 n 个点的集合，其中 k 位于 P 的凸包 CH(P) 的内部。当且仅当所有顶点都具有偶（奇）度数时，我们称 P 的三角剖分 T 为偶（奇）度，如果至少 k 个内部顶点具有偶（奇）度数，则称为伪偶（伪奇）。学位。一方面，所有内部顶点均为偶数的三角剖分有一个很好的性质；它们的顶点可以是 3 色，参见（Heawood in Quart J Pure Math 29:270–285, 1898，Steinberg in A source book for Challenges and Direction, vol 55。Elsevier，阿姆斯特丹，第 211–248 页，1993，Diks et al. in Lecture Notes in Computer Science，第 2573 卷。Springer，柏林，第 55 页。 138-149，2002）。另一方面，奇怪的三角剖分最近在 Erdős 和 Szekeres 的经典“幸福结局问题”的彩色版本中得到了应用，参见（Aichholzer 等人，SIAM J Discrete Math 23(4):2147–2155, 2010）。很容易证明存在既不允许伪偶三角剖分也不允许伪奇三角剖分的点集。尽管如此，在本文中，我们展示了如何构造一组大小最多为 $${\frac{k}{3} + c}$$k3+c 的 Steiner 点集 S = S(P)，其中 c 是正常数，这样可以在 $${P \cup S}$$P∪S 上构造伪偶（伪奇）三角剖分。此外，我们还表明，偶（奇）三角剖分始终可以使用最多 $${\frac{n}{3} + c}$$n3+c 施泰纳点来构造，其中 c 又是一个正常数。我们的构造具有以下性质：除了最多两个施泰纳点之外，所有施泰纳点都位于 CH(P) 的内部。
Let $${P\subset\mathbb{R}^{2}}$$P⊂R2 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 $${\frac{k}{3} + c}$$k3+c , where c is a positive constant, such that a pseudo-even (pseudo-odd) triangulation can be constructed on $${P \cup S}$$P∪S . Moreover, we also show that even (odd) triangulations can always be constructed using at most $${\frac{n}{3} + c}$$n3+c 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).