On an estimate of the size of the maximum matching for a family of disjoint compact convex sets in the plane

DOI10.1016/S0166-218X(01)00202-5MaRDI QIDQ5951972zbMATH OpenWikidataFDO

Authors Kiyoshi Hosono

Publication date 2001

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0166-218X(01)00202-5

zbMATH Keywords

computational geometrymatchingvisibility graph

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Convex sets in (2) dimensions (including convex curves) (52A10) Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Review text

Consider \(2n\) disjoint compact convex sets in the plane all having the same width in some direction.NEWLINENEWLINENEWLINEThe author's main theorem says that always \([2n/3]\) pairs of the sets can be matched by disjoint line segments and that it is possible that not more than \([4n/5]\) pairs can be matched.NEWLINENEWLINENEWLINEThe paper ends with two conjectures.

Recommendations

• The size of maximal almost disjoint families
• On certain Matching Properties of Convex Sets
• Extremal theory for convex matchings in convex geometric graphs
• Tight bounds on maximal and maximum matchings
• scientific article; zbMATH DE number 2081000
• A compactness result for perfect matchings
• Bounds on maximum \(b\)-matchings
• Two problems on matchings in set families -- in the footsteps of Erdős and Kleitman
• Tight lower bounds on the size of a maximum matching in a regular graph
• On the maximum number of points in a maximal intersecting family of finite sets

Cites work

• Approximation algorithms for the Geometric Covering Salesman Problem
• Computing simple circuits from a set of line segments
• Computing Simple Circuits from a Set of Line Segments is NP-Complete
• Hamiltonian triangulations and circumscribing polygons of disjoint line segments
• scientific article; zbMATH DE number 4065813 (Why is no real title available?)
• scientific article; zbMATH DE number 1033560 (Why is no real title available?)
• scientific article; zbMATH DE number 1182918 (Why is no real title available?)
• On the visibility graph of convex translates

Cited in

(4)

• On the perfect matching of disjoint compact sets by noncrossing line segments in \(\mathbb R^n\)
• An upper bound on the size of separated matchings
• Tight bounds for visibility matching of \(f\)-equal width objects
• Large convex sets in difference sets

This page was built for publication: On an estimate of the size of the maximum matching for a family of disjoint compact convex sets in the plane

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5951972)