/^creative ^commor
ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 15 (2018) 375-382
https://doi.org/10.26493/1855-3974.1228.d7d
(Also available at http://amc-journal.eu)
Touching perfect matchings and halving lines
Micha A. Perles
Institute of Mathematics, The Hebrew University, Jerusalem, Israel
Horst Martini
Fakultät fur Mathematik, Technische Universität Chemnitz, Germany
Yaakov S. Kupitz
Institute of Mathematics, The Hebrew University, Jerusalem, Israel
Received 10 November 2016, accepted 4 March 2018, published online 10 July 2018 Abstract
Let V be a set of 2m (1 < m < to) points in the plane. Two segments I, J with endpoints in V cross if relint I n 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. Math. Subj. Class.: 05C62, 68R10, 52C35
1 Introduction, notions and main results
Let V be a set of 2m distinct points in the plane R2 (1 < m < to). By a (perfect geometric) matching of V we mean a set M = [Ii,..., Im } of m non-degenerate closed line segments whose endpoints are (all) the points of V. The number of matchings of V is
(2m - 1)!! = fi(2i - 1) = 2g .
E-mail addresses: perles@math.huji.ac.il (Micha A. Perles), martini@mathematik.tu-chemnitz.de (Horst Martini), kupitz@math.huji.ac.il (Yaakov S. Kupitz)
©® This work is licensed under https://creativecommons.org/licenses/by/3.0/
376
Ars Math. Contemp. 15 (2018) 441-466
If V is in general position (no three points on a line), then two distinct segments I, J e M may be
(a)	disjoint (I n J = 0),
(b)	or they may cross, i.e., share a unique point that lies in the relative interior of both I and J.
When V is unrestricted, two more possibilities arise.
(c)	The unique common point of I and J maybe an interior point of I and an endpoint of J (or vice versa).
(d)	If the four endpoints of I and J are collinear, then I and J may share a line segment. (This includes the possibility that I C relint J, or vice versa.)
We shall say that two segments I, J touch if they have at least one point in common (In J = 0). We call M a simple matching (SM) if the segments of M are pairwise disjoint.
It is well known and quite easy to show (see [2, Theorem 4.2]) that if V is in general position, then the number sm( V) of simple matchings on V is bounded from below by the m-th Catalan number Cm, i.e.,
Equality holds for m =1 or when V is the set of vertices of a convex 2m-gon. (It can be shown that if V is in general position but not in convex position, then sm(V) > Cm, with only one exception: when m = 3 and V consists of the vertices of a convex pentagon P plus a sixth point that lies in the interior of the pentagon formed by the diagonals of P.)
Call M a cross-matching (CM) if each two distinct segments of M cross. Let us call M a touching matching (TM) if every two segments of M touch.
1.1	Halving lines
Definition 1.1. A line L is a halving line of V if each of the two open half-planes L+, L-bounded by L contains fewer than m points of V.
This clearly implies that |L n V | > 2, i.e., that the line L is spanned by V. When V is in general position, then necessarily |L n V| = 2, and |L- n V| = |L+ n V| = m — 1. When V is unrestricted we call L a halving line of order k if max(|L- n V |, |L+ n V |) = m — k (1 < k < m). In that case we may assume that, say, |L+ n V| = m — k, |L- n V| = m — k — e, and |L n V| = 2k + e, for some e, 0 < e < m — k. (See Figure 1.)
1.2	Halving lines and TMs
If M is a TM on V, I is a segment of M, and L = aff I is the line spanned by I, then L is a halving line. Indeed, an open half-plane bounded by L contains no endpoint of I, and at most one endpoint of each other segment of M.
The connection between the number h( V) of halving lines of V, and the existence of a cross-matching on V, in the case where V is in general position, was established by Pach and Solymosi in [3] as follows: They observed that each point of V lies on at least one halving line, hence h(V) > m. Then they found that either each point of V lies on just one
(1.1)
M. A. Perles et al.: Touching perfect matchings and halving lines
377
halving line, h( V) = m and V admits a unique CM, or at least one point of V lies on more than one halving line, h( V) > m, and V admits no CM at all. This result was generalized in [1] (see Theorem 1 and Corollary 3 there). In [4] we prove an extremal property of CMs, namely that if V admits a CM M, and M' is another (perfect) geometric matching on V, then the sum of the (Euclidean) lengths of the edges of M' is strictly less than the sum of the lengths of the edges of M. An analogous result holds for TMs. The geometric graph whose edges span (all) the halving lines of its vertex set V (with | V | even and V in general position) is said to be a bigraph. We refer to [5] regarding results on bigraphs.
The aim of this note is to extend the result of [3] to arbitrary, unrestricted 2m-subsets V of R2.
In the next section we define the notion of "a halving line at a point p e V", and show that a halving line of order k is a halving line at exactly 2k points. We also show that the number of halving lines at any point p e V is odd, hence > 1. The main results can be summarized as follows:
Theorem 1.2. Suppose L1,... ,Lt (t = h(V)) are all the halving lines of V, with Li of order ki (1 < ki < m, i = 1,... ,t). If for each p e V there is just one halving line at p, then
and V has no TM.
In particular we have
Corollary 1.3. The set V has a unique TM iff V has exactly m halving lines, each of order 1. The unique TM is a CM if each of the m halving lines contains just two points of V.
i=1
and the number of TMs of V is precisely
ncki!)-
i= 1
If, for some p e V, there is more than one halving line at p, then
i=i
|V n L+1 = m - k
ak ak-1
a1 b1 b2 be c1 c2 |V n L-1 = m - k - e
Figure 1: A halving line of order k.
378
Ars Math. Contemp. 15 (2018) 441-466
2 Proofs
We start with the definition of "a halving line of V at p", where V is a set of 2m points in R2, and p G V. For a point p G V and a unit vector u = (u1,u2), denote by L(p, u) the directed line {p + Au : A G R}. (The direction is from small A to larger A.) Note that L(p, -u) is the same line, directed backwards. Define u+ = (-u2,u1),
L(p,u)F = L(p,u) + : ^ > 0}, and L(p,u)B = L(p,u) + : ^ < 0}.
F and B stand for "Front" and "Back", respectively.
L(p, u)F and L(p, u)B are the two open half-planes bounded by L(p, u). Now move the unit vector u continuously on the unit circle in counterclockwise direction. Note that
L(p, u) F and L(p, u)B switch when u is replaced by -u. As long as L(p, u) does not meet V \ {p}, we find that
|V n L(p,u)F | + |V n L(p,u)B | = |V - {p}| = 2m - 1,
and therefore one side of L(p, u) (the "major" side) contains at least m points of V, whereas the other side (the "minor" side) contains at most m - 1 points of V.
As we change the direction u, the major side of L(p, u) will remain (Front or Back) as long as the rotating line L(p,u) does not meet V \ {p}. We call L(p,uo) a halving line of V at p if the major side of L(p,u) switches (from B to F or vice versa) as u passes through uo.
Proposition 2.1. If L = L(p, uo) is a halving line of V at p, then L is a halving line of V.
Proof. We must show that both open sides of L, L(p, uo)F and L(p, uo)B, contain fewer than m points of V each. If, say, | VnL(p, uo)F | > m, then VnL(p, u)F D VnL(p, uo)F, and therefore |V n L(p,u)F| > m, for all unit vectors u sufficiently close to uo, on both sides of uo, so the major side of L(p, u) does not switch at u = uo.	□
Proposition 2.2. For each point p G V, the number of halving lines of V at p is odd (hence > 1).
Proof. Choose an initial direction uo, such that V n L(p,uo) = {p}. Suppose the major side of L(p, uo) is, say, L(p, uo)F. Rotate the line throughp counterclockwise by 180°, i.e., move u along a semicircle, until we reach L(p, -uo). Now the major side is L(p, -uo)B (= L(p, uo)F). We conclude that on the way the major side switched (from F to B or vice versa) an odd number of times.	□
Proposition 2.3. Suppose L is a halving line of V of order k (1 < k < m). Then L is a halving line of V at p for exactly 2k points of V.
Proof. Assume, w.l.o.g., that
|V n L-| = m - k - £, |V n L+| = m - k, and |V n L| = 2k + e, for some 0 < e < m - k. Label the points of V n L in order
ak, ak-i, .. ., a1,b1, .. . ,b£,c1,. .., ck,
M. A. Perles et al.: Touching perfect matchings and halving lines
379
as in Figure 1. Fix a point p G V n L, and consider a line that rotates counterclockwise through p. As the rotating line passes through the horizontal position (see Figure 1), the major side switches from Above to Below if p is one of the a»'s, and from Below to Above if p is one of the c's. But if p is one of the b»'s, then the major side remains Above (at least in a small neighborhood on both sides of the horizontal position).	□
Next we show that if L is a halving line of V of order k, as in Figure 1, and M is a TM on V, then M matches the aj's with the c/s (and vice versa).
Proposition 2.4. Suppose V = S U T is a partition of V into two sets of equal size (|S| = |T| = m), and conv S n conv T = 0. If M is a TM of V, then each segment I G M connects a point of S with a point of T.
Proof. Assume, on the contrary, that some segment I G M has both endpoints in S. This leaves (at most) m - 2 points of S to be matched to points of T, and thus some other segment J G M has both endpoints in T. But then I n J C conv S n conv T = 0. □
Now look again at the halving line L in Figure 1. Define A = {a^ ..., ak}, B = jbi, ...,6J, C = {ci, ...,ck}, D_ = B U (V n L_) and D+ = V n L+ (|D_| = |D+| = m - k). Applying Proposition 2.4 twice, first with S = A U D_, T = C U D+, and then with S' = C U D_, T' = A U D+, we find:
Proposition 2.5. If M is a TM of V, then each segment I G M with one endpoint in A has its other endpoint in C (and vice versa), and each segment J G M with one endpoint in D_ has its other endpoint in D+ (and vice versa).
Note also that for any permutation 0 of {1,2,..., k}, the intersection of the k segments [a», c^)] (i = 1,..., k) is the segment [a1, c1], that connects the k'th point of V n L from the right with the k'th point of V n L from the left. We call this segment [a1, c1] the central segment of the halving line L.
Suppose L1,..., Lt (t = h(V)) are all the halving lines of V, with L» of order k» for i = 1,... , t. For p G V, denote by h(p) the number of halving lines at p. In view of Propositions 2.1 - 2.3, we have
4 1 k» = 2 h(p) - m,
i=1	pev
with equality (= m) iff h(p) = 1 for all p G V.
Proposition 2.6. If h(p) > 1 for some p G V, then there is no TM on V.
Proof. Suppose, on the contrary, that V admits a TM M. Let I = [p, q] be a segment in M with one endpoint p. Let L, L' be two different halving lines of V at p (h(p) > 1). By Proposition 2.5 we have q G L n L'. But L n L' = {p}.	□
Assume, from now on, that h(p) = 1 for all p G V. Thus J21=1 k» = m. In other words, on each line L» we can match two disjoint subsets of V n L», each of order k», A» (the kj "leftmost" points of V n L») and C» (the k» "rightmost" points of V n L»). L» is a halving line of Vat p iff p G A» U C». The sets A1, C1,..., At, Ct form a partition of V. As we have seen in Proposition 2.5, any TM of V will match the points of A» with those of C».
380
Ars Math. Contemp. 15 (2018) 441-466
There are k! ways to match A with Cj, and in each of these matchings, the intersection of the connecting segments is the "central segment" of the halving line L. To show that the individual TM's of A U Cj on L (i = 1,...,t) yield a TM of V, it suffices to show that the central segments of different halving lines L and Lj do meet (assuming, of course, that h(p) = 1 for all p G V). This will be done in the next proposition.
Proposition 2.7. Suppose L is a halving line of V of order k, with V n L labelled ak,..., ai, bi,..., be, c^ ..., ck as in Figure 1, A = {ak,..., ai}, C = {ci,..., ck}, and let L' be another halving line of V, of order k', with V n L' labelled similarly: a'k,,..., ai, bi, ..., b', ,ci,...,c'k/, A' = {a'k,, ...,ai}, C' = {ci,...,c'k,}. If the central segments [ai, ci] (of L) and [ai, ci] (of L') do not meet, then h(p) > 1 for some p G {ai, ci, ai, ci}.
Proof. The two distinct lines L, L' cannot be parallel. If they are, and L' lies, say, above L, then the open side L+ of L includes the closed side cl L'+ of L', and therefore | V n L+1 > |V n cl L'+| > m, which is impossible. Let z be the crossing point of L and L', and suppose, w.l.o.g., that z misses the central segment [ai, ci] of L, and lies to the left of ai on L, see Figure 2.
L' , L"
L
z / ai
ci
Figure 2: Proof of Proposition 2.7.
Consider a directed line that rotates counter-clockwise through ai. As it passes through L (directed from left to right), the major side of V switches from Front to Back. As it reaches L'' (parallel to L'), or any direction sufficiently close to that of L', the major side of V is again Front, since the open half-plane to the left of L'' includes the closed half-plane to the left of L', which in turn contains at least m + k' points of V. Thus, there must have been another switch from Back to Front on the way, or, in other words, h(ai) > 1. □
3 Algorithmic aspects
The insights gained in the earlier sections of this note can be used to device an algorithm that decides whether a set P c R2 (|P| = 2m) admits a TM, and to find a TM (or all TMs) if one exists. The algorithm is conceptually simple, and seems to be also computationally quite effective, though not as efficient as the one proposed in [3] (m2 vs. m log m).
Step 1: Find the point po = (x0, yo) G P that is the first in P with respect to the lexicographic order of points (x, y) G R2. p0 is a vertex of the convex hull [P] = conv P.
Step 2: Calculate the slopes of the 2m - 1 segments [p0,p] (p G P \ {p0}), arrange them in non-decreasing order and find the median slope (this can be shared by several
M. A. Perles et al.: Touching perfect matchings and halving lines
381
segments, of course). This slope determines the (unique) halving line L of P at p0. Find the number of points of P that lie below L, on L and above L, and order the points of P n L lexicographically. This enables us to determine the order k of the halving line L, and the sets A, C consisting of the first (resp. last) k points of P n L. These are the 2k points p € P n L such that L is a halving line at p. Erase these 2k points, and call the remaining set P' (|P= 2(m - k)). If P' = 0, stop. Otherwise, return to Step 1 with P replaced by P'.
To see that this really works, we make the following observations:
(A) If P admits a TM M, then M contains k segments (on L) that connect points of A with points of C. The rest of M is a TM of P' (= P \ (A U C)). Moreover, if L is any halving line of P other than L, of order k, then removal of A U C leaves L a halving line of P' of the same order k. This is clear when the central segments of L and of L meet at a point that is interior to the central segment [ai, ci] of L. In that case we lose k points on each side of L.
The case when the common point of these two central segments is an endpoint, say a1, of [a1, c1], is shown in Figure 3. (The reason why C is included in L+ and not in Lis given below.)
Figure 3: Two central segments whose common point is an endpoint in one of them.
Since M matches P n L + with (P n L-) U B and a1 (ai G B and ai G A c P n L) with some point of C (Proposition 2.5), C c PnL+ (as in Figure 3). Thus, removing
A U C will reduce |P n L+1 by k to (m - k) - P n B by 1 to e - 1 (> 0, since a1 G B?1), and |P n L-1 by k - 1 to (m - k) - k - (e - 1).
(B) If M' is a TM of P', and N is a matching of A to C (on P n L), then M = M' U N is a TM of P iff the central segment [a1, c1] of L meets the central segment of each halving line of P'. Thus, if applying our algorithm to P' we find that P' has no TM, then the same holds for P. If P' does admit a TM, then P has a TM iff the central segment of L meets the central segment of each halving line of P'. To check this, we may need O(m2) operations.
References
[1] A. Andrzejak, B. Aronov, S. Har-Peled, R. Seidel and E. Welzl, Results on k-sets and j-facets via continuous motion, in: R. Janardan (ed.), Proceedings of the Fourteenth Annual Symposium on Computational Geometry, New York, NY, pp. 192-199, 1998, doi:10.1145/276884.276906,
382
Ars Math. Contemp. 15 (2018) 441-466
proceedings of the 14th ACM Symposium on Computational Geometry (SCG '98) held in Minneapolis, MN, June 07 - 10, 1998.
[2]	A. Garcia, M. Noy and J. Tejel, Lower bounds on the number of crossing-free subgraphs of KN, Comput. Geom. 16 (2000), 211-221, doi:10.1016/s0925-7721(00)00010-9.
[3]	J. Pach and J. Solymosi, Halving lines and perfect cross-matchings, in: B. Chazelle, J. E. Goodman and R. Pollack (eds.), Advances in Discrete and Computational Geometry, American Mathematical Society, Providence, RI, volume 223 of Contemporary Mathematics, pp. 245-249, 1999, doi:10.1090/conm/223/03141, proceedings of the AMS-IMS-SIAM Joint Summer Research Conference on Discrete and Computational Geometry: Ten Years Later held at Mount Holyoke College, South Hadley, MA, July 14- 18, 1996.
[4]	M. A. Perles, H. Martini, Y. S. Kupitz, H. Last and R. Pinchasi, Cross-matchings and circuits have maximal length, in preparation.
[5]	G. J. Simmons and R. C. Entringer, Some properties of components of bigraphs, Period. Math. Hungar. 3 (1973), 167-174, doi:10.1007/bf02018472.