Touching perfect matchings and halving lines

Micha A. Perles, Horst Martini, Yaakov S. Kupitz


Let V be a set of 2m (1 ≤ m < ∞) points in the plane. Two segments I, J with endpoints in V cross if relint I ∩ relint J is a singleton. A (perfect) cross-matching M on V is a set of m segments with endpoints in V such that every two segments in M cross. A halving line of V is a line l spanned by two points of V such that each one of the two open half planes bounded by l contains fewer than m points of V. Pach and Solymosi proved that if V is in general position, then V admits a perfect cross-matching iff V has exactly m halving lines. The aim of this note is to extend this result to the general case (where V is unrestricted).


Bigraphs, cross-matching, halving lines, perfect matchings

Full Text:



ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications