Paper Info
Title
On an estimate of the size of the maximum matching for a family of disjoint compact convex sets in the plane
Abstract
Let C be any family of 2 n disjoint compact convex sets in the plane. If C has f-equal width for some direction f , then ⌊2 n /3⌋ pairs of elements in C can always be matched by disjoint line segments and more than ⌊4 n /5⌋ pairs cannot occasionally be matched. Furthermore, if C is a family of translates of the set satisfying a certain constraint, then ⌊4 n /5⌋ pairs of elements can always be matched by disjoint line segments.
Year
DOI
Venue
2001
10.1016/S0166-218X(01)00202-5
Discrete Applied Mathematics
Keywords
Field
DocType
visibility graph,maximum matching,computational geometry,disjoint compact convex set,matching,satisfiability,convex set
Line segment,Discrete mathematics,Combinatorics,Disjoint sets,Visibility graph,Hamiltonian path,Computational geometry,Regular polygon,Matching (graph theory),Disjoint union,Mathematics
Journal
Volume
Issue
ISSN
113
2-3
Discrete Applied Mathematics
Citations 
PageRank 
References 
0
0.34
5
Authors
1
Name
Order
Citations
PageRank
Kiyoshi Hosono16011.01