Spanning trees of multicoloured point sets with few intersections
Por:
Leaños J., Merino C., Salazar G., Urrutia J.
Publicada:
1 ene 2005
Resumen:
Kano et al. proved that if P 0, P 1, ..., P k-1 are pairwise disjoint collections of points in general position, then there exist spanning trees T 0, T 1, ..., T k-1, of P 0, P 1, ..., P k-1, respectively, such that the edges of T 0?T 1? ??T k-1 intersect in at most (k-1)n-k(k-1)/2 points, In this paper we show that this result is asymptotically tight within a factor of 3/2, To prove this, we consider alternating collections, that is, collections such that the points in P := P 0?P 1 ???P k-1 are in convex position, and the points of the Pi's alternate in the convex hull of P. © Springer-Verlag Berlin Heidelberg 2005.
Filiaciones:
Leaños J.:
Facultad de Ciencias, UASLP, San Luis Potosí, Mexico
Merino C.:
Instituto de Matemáticas, UNAM, México, Mexico
Salazar G.:
Instituto de Investigación en Comunicación Óptica, UASLP, San Luis Potosí, Mexico
Urrutia J.:
Instituto de Matemáticas, UNAM, México, Mexico
|