Properly colored geometric matchings and 3-trees without crossings on multicolored points in the plane
Properly colored geometric matchings and 3-trees without crossings on multicolored points in the plane
复制标题
正确着色的几何匹配和三棵树，在平面上的多色点上没有交叉
DOI：
10.1007/978-3-319-13287-7_9
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Miyuki
中科院分区：
文献类型：
--
作者：
Kano;Mikio; Suzuki;Kazuhiro; Uno;Miyuki
假设平面上有一组彩色点，其中没有三个点共线，并且每种颜色最多出现在最多点上。我们证明了（如果是偶数）上非交叉正确着色几何完美匹配的存在性，以及最大度数最大的非交叉正确着色几何生成树的存在性。此外，我们证明了平面晶格中非交叉正确着色几何完美匹配的存在。为了证明我们的结果，我们提出了一个有用的引理，它给出了彩色点序列的良好划分。
Letbe a set of multicolored points in the plane such that no three points are collinear and each color appears on at mostpoints. We show the existence of a non-crossing properly colored geometric perfect matching on(ifis even), and the existence of a non-crossing properly colored geometric spanning tree with maximum degree at moston. Moreover, we show the existence of a non-crossing properly colored geometric perfect matching in the plane lattice. In order to prove these our results, we propose an useful lemma that gives a good partition of a sequence of multicolored points.