Repositorio Atenea de la Facultad de Ciencias, UNAM >
Repositorio Ciencias >
FACULTAD DE CIENCIAS >
Ciencias >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/11154/2393
|
Title: | Spanning trees of multicoloured point sets with few intersections |
Authors: | Leanos, J Merino, C Salazar, G Urrutia, J |
Issue Date: | 2005 |
Abstract: | Kano et al. proved that if P-0, P-1,..., Pk-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,...,Pk-1, respectively, such that the edges of T-0 boolean OR T-1 boolean OR (...) boolean OR Tk-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 boolean OR P-1 boolean OR (...) boolean OR Pk-1 are in convex position, and the points of the Pi's alternate in the convex hull of P. |
URI: | http://hdl.handle.net/11154/2393 |
ISSN: | 0302-9743 |
Appears in Collections: | Ciencias
|
Files in This Item:
There are no files associated with this item.
|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
|