Quadrangulations on 3-colored point sets with Steiner points and their winding number
Quadrangulations on 3-colored point sets with Steiner points and their winding number
复制标题
具有 Steiner 点及其绕数的 3 色点集上的四边形
DOI：
10.1007/s00373-013-1346-4
复制
发表时间：
2014
影响因子：
0.7
通讯作者：
Atsuhiro Nakamoto
中科院分区：
文献类型：
--
作者：
Sho Kato;Ryuich Mori; Atsuhiro Nakamoto
设P是平面上的一个点集，考虑Pis是否是四边形的，即是否存在一个2连通平面图G，G的每条边都是一条直段，使得V（G）=P，G的外圈与P的凸船体Conv（P）重合，G的每个有限面都是四边形的。很容易看出，这是可能的，当且仅当偶数个点的Plie上的Conv（P）。因此，我们给P的ak-染色，并考虑同样的问题，避免边连接两个顶点的P具有相同的颜色。在这种情况下，我们总是假设Conv（P）上的Plying点的数量是偶数，并且Conv（P）上的任何两个连续点都有不同的颜色。然而，对于任意k ≥ 2，存在k-着色的非四边形点集P.因此我们引入了Steiner点，它可以放在Conv（P）内部的任何位置，并且每个点可以被任意k种颜色着色。当k = 2时，Alvarez等人证明了如果平面上的点集P在一般位置上由红点和蓝点组成，则添加Steiner点Q，P <$Q是可四边形化的，但存在不可四边形化的三色点集，无论添加多少Steiner点。本文定义了三色点集P的缠绕数，证明了三色点集P_n一般位置加上有限个Steiner点集Q是可四边形化的当且仅当P的缠绕数为零。当P ∈ Q是可四边形化的时，我们证明了，其中|P| = Pin Conv（P）的点数为2 m。
LetPbe a point set on the plane, and consider whetherPisquadrangulatable, that is, whether there exists a 2-connected plane graphGwith each edge a straight segment such thatV(G) =P, that the outer cycle ofGcoincides with the convex hull Conv(P) ofP, and that each finite face ofGis quadrilateral. It is easy to see that it is possible if and only if an even number of points ofPlie on Conv(P). Hence we give ak-coloring toP, and consider the same problem, avoiding edges joining two vertices ofPwith the same color. In this case, we always assume that the number of points ofPlying on Conv(P) is even and that any two consecutive points on Conv(P) have distinct colors. However, for everyk≥ 2, there is ak-colored non-quadrangulatable point setP. So we introduceSteiner points, which can be put in any position of the interior of Conv(P) and each of which may be colored by any of thekcolors. Whenk= 2, Alvarez et al. proved that if a point setPon the plane consists ofred andblue points in general position, then adding Steiner pointsQwith,P∪Qis quadrangulatable, but there exists a non-quadrangulatable 3-colored point set for which no matter how many Steiner points are added. In this paper, we define thewinding numberfor a 3-colored point setP, and prove that a 3-colored point setPin general position with a finite setQof Steiner points added is quadrangulatable if and only if the winding number ofPis zero. WhenP∪Qis quadrangulatable, we prove, where |P| =nand the number of points ofPin Conv(P) is 2m.