Bichromatic Quadrangulations with Steiner Points
Bichromatic Quadrangulations with Steiner Points
复制标题
具有斯坦纳点的双色四边形
DOI：
10.1007/s00373-007-0715-2
复制
发表时间：
2007
影响因子：
0.7
通讯作者：
J. Urrutia
中科院分区：
文献类型：
--
作者：
V. Álvarez;T. Sakai;J. Urrutia
设P为一般位置上的ak着色点集，k≥ 2.一族具有不相交边的四边形称为Pif的四边形，所有连接点的边具有不同的颜色，和。一般来说，很容易看出，并非所有着色的点集都允许四边形化;当它们允许时，我们称它们为可四边形化的。对于一个可四边形化的点集，它必须满足它的凸船体Conv（P）有偶数个点，并且Conv（P）的连续顶点接收不同的颜色。本文研究了如下类型的问题：设P是ak-着色点集。我们需要在Conv（P）的边界上加上多少个Steiner点才能使它可四边形化？当k = 2时，我们通常称P为双色点集，其色类通常用RandB表示，即P的红、蓝元素。在本文中，我们证明了任何双色点集，|R| = |B| = n可以通过添加最多的Steiner点来使四边形化，并且有时需要Steiner点。为了证明后者，我们还表明，任何单色点集Pofnelements的凸船体总是可以划分成一组星形多边形与不相交的内部，其中，和。对于n = 3 k，这个界是紧的。最后，我们证明了存在3-着色点集不能完备为3-四边形点集。
LetPbe ak colored point setin general position,k≥ 2. A family of quadrilaterals with disjoint interiorsis called a quadrangulation ofPif, the edges of alljoin points with different colors, and. In general it is easy to see that not allk-colored point sets admit a quadrangulation; when they do, we call them quadrangulatable. For a point set to be quadrangulatable it must satisfy that its convex hull Conv(P) has an even number of points and that consecutive vertices of Conv(P) receive different colors. This will be assumed from now on. In this paper, we study the following type of questions: LetPbe ak-colored point set. How many Steiner pointsin the interiorof Conv(P) do we need to add toPto make it quadrangulatable? Whenk= 2, we usually callPa bichromatic point set, and its color classes are usually denoted byRandB, i.e. the red and blue elements ofP. In this paper, we prove that any bichromatic point setwhere |R| = |B| =ncan be made quadrangulatable by adding at mostSteiner points and thatSteiner points are occasionally necessary. To prove the latter, we also show that the convex hull of any monochromatic point setPofnelements can be always partitioned into a setof star-shaped polygons with disjoint interiors, where, and. Forn= 3kthis bound is tight. Finally, we prove that there are 3-colored point sets that cannot be completed to 3-quadrangulatable point sets.