|
|||||
|
|
Connecting colored point sets |
|
| Authors: | Oswin Aichholzer Clemens Huemer |
| Institution: | a Institute for Software Technology, University of Technology, Graz, Austria b Institute for Theoretical Computer Science, University of Technology, Graz, Austria c Institute for Software Technology, University of Technology, Graz, Austria d Dept. Mat. Aplicada II, Universitat Politecnica de Catalunya, Barcelona, Spain |
| Abstract: | We study the following Ramsey-type problem. Let S=B∪R 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 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) and T(R). |
| Keywords: | Bicolored point set Spanning trees Crossing properties |
| 本文献已被 ScienceDirect 等数据库收录！ | |