On Convex Quadrangulations of Point Sets on the Plane
On Convex Quadrangulations of Point Sets on the Plane
复制标题
关于平面上点集的凸四边形
DOI：
10.1007/978-3-540-70666-3_5
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
J. Urrutia
中科院分区：
文献类型：
--
作者：
V. M. Heredia;J. Urrutia
设Pn是平面上一般位置上的n个点的集合，n≥ 4. Pn的凸四边形化是将Pn的凸壳划分成一组四边形，使得它们的顶点是Pn的元素，并且Pn的元素不位于任何四边形的内部。很容易看出，如果P允许四边形化，它的凸船体必须有偶数个顶点。文[6]证明了：若Pn的凸船体有偶数个点，则在其凸船体的内部增加最多个Steiner点，总可得到一个允许凸四边形的点集。作者还表明，斯坦纳点有时是必要的。本文给出了如何分别改进[6]的上界和下界.事实上，在本文中，我们证明了一个上界的n，并与一个长期和没有启发性的情况下分析（超过50例！）我们可以将上界改进为，详情见[9]。
LetPnbe a set ofnpoints on the plane in general position,n≥ 4. Aconvex quadrangulationofPnis a partitioning of the convex hullofPninto a set of quadrilaterals such that their vertices are elements ofPn, and no element ofPnlies in the interior of any quadrilateral. It is straightforward to see that ifPadmits a quadrilaterization, its convex hull must have an even number of vertices. In [6] it was proved that if the convex hull ofPnhas an even number of points, then by adding at mostSteiner points in the interior of its convex hull, we can always obtain a point set that admits a convex quadrangulation. The authors also show thatSteiner points are sometimes necessary. In this paper we show how to improve the upper and lower bounds of [6] toand torespectively. In fact, in this paper we prove an upper bound ofn, and with a long and unenlightening case analysis (over fifty cases!) we can improve the upper bound to, for details see [9].