Spanning trees of multicoloured point sets with few intersections
Conference Paper
Overview
Research
Identity
Additional Document Info
View All
Overview
abstract
Kano et al. proved that if P0, P1, ..., P k-1 are pairwise disjoint collections of points in general position, then there exist spanning trees T0, T1, ..., T k-1, of P0, P1, ..., Pk-1, respectively, such that the edges of T0∪T1∪ ⋯∪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 := P0∪P1 ∪⋯∪Pk-1 are in convex position, and the points of the Pi%27s alternate in the convex hull of P. © Springer-Verlag Berlin Heidelberg 2005.
Kano et al. proved that if P0, P1, ..., P k-1 are pairwise disjoint collections of points in general position, then there exist spanning trees T0, T1, ..., T k-1, of P0, P1, ..., Pk-1, respectively, such that the edges of T0∪T1∪ ⋯∪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 := P0∪P1 ∪⋯∪Pk-1 are in convex position, and the points of the Pi's alternate in the convex hull of P. © Springer-Verlag Berlin Heidelberg 2005.
publication date
published in
Research
keywords
Asymptotic stability; Color codes; Combinatorial mathematics; Set theory; Trees (mathematics); Convex hulls; Disjoint collections; Position detection; Computational geometry
Identity
Digital Object Identifier (DOI)
Additional Document Info
start page
end page
volume