On the intersection number of matchings and minimum weight perfect matchings of multicolored point sets
Article
-
- Overview
-
- Research
-
- Identity
-
- Additional Document Info
-
- View All
-
Overview
abstract
-
Let P and Q be disjoint point sets with 2r and 2s elements respectively, and M 1 and M 2 be their minimum weight perfect matchings (with respect to edge lengths). We prove that the edges of M 1 and M 2 intersect at most |M 1|%2b|M 2|-1 times. This bound is tight. We also prove that P and Q have perfect matchings (not necessarily of minimum weight) such that their edges intersect at most min{r,s} times. This bound is also sharp. © Springer-Verlag 2005.
publication date
published in
Research
keywords
-
Geometric graphs; Minimum weight perfect matchings; Perfect matchings
Identity
Digital Object Identifier (DOI)
Additional Document Info
start page
end page
volume
issue