Touching perfect matchings and halving lines

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

Abstract


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).


Keywords


Bigraphs, cross-matching, halving lines, perfect matchings

Full Text:

PDF ABSTRACTS (EN/SI)


DOI: https://doi.org/10.26493/1855-3974.1228.d7d

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