Connecting colored point sets
详细信息 查看全文
- 作者：Oswin Aichholzer ; Franz Aurenhammer ; Thomas Hackl ; Clemens Huemer
- 关键词：Bicolored point set ; Spanning trees ; Crossing properties
- 刊名：Discrete Applied Mathematics
- 出版年：2007
- 出版时间：1 February 2007
- 年：2007
- 卷：155
- 期：3
- 页码：271-278
- 全文大小：162 K
文摘
We study the following Ramsey-type problem. Let S=BR be a two-colored set of n points in the plane. We show how to construct, in time, a crossing-free spanning tree T(B) for B, and a crossing-free spanning tree T(R) for R, such that both the number of crossings between 6808183eb035c00a83d"" title=""Click to view the MathML source"">T(B) and T(R) and the diameters of T(B) and T(R) are kept small. The algorithm is conceptually simple and is implementable without using any non-trivial data structure. This improves over a previous method in Tokunaga [Intersection number of two connected geometric graphs, Inform. Process. Lett. 59 (1996) 331–333] that is less efficient in implementation and does not guarantee a diameter bound. Implicit to our approach is a new proof for the result in the reference above on the minimum number of crossings between T(B) andT(R).