ICCG 2022, Sharif UT, February 24, 2022

A Randomized Algorithm for Non-crossing Matching of Online Points
Shahin Kamali∗

Pooya Nikbakht†

Abstract
We study randomized algorithms for the online noncrossing matching problem. Given a sequence of n online points in general position, the goal is to create amatching of maximum size so that the line segments
connecting pairs of matched points do not cross. In
previous work, Bose et al. [CCCG 2020] showed that asimple greedy algorithm matches at least ⌈2n/3−1/3⌉ ≈0.6̄n points, and it is the best that any deterministic
algorithm can achieve. In this paper, we show that randomization helps to achieve a better competitive ratio,that is, we present a randomized algorithm that matches
at least 235n/351 − 202/351 ≈ 0.6695n points.
1

Introduction

In the geometric matching problems, the input is a setof geometric objects, and the goal is to create a pairwise matching of these objects under different restrictions and objectives. In the bottleneck matching problem, for example, the goal is to create a perfect matching of n points, assuming n is even, so as to minimize
the maximum length of the line segments that connect
matched pairs [8]. Using the same terminology as ingraph theory, we refer to the line segments that connect
pairs of matched vertices as the edges of the matching.
Other variants of the geometric matching problems ask
for perfect matchings that minimize the total length ofedges [4] or maximize the length of the shortest edge
[6]. Matching objects other than points are also studied(see, e.g., [1, 2])
In the non-crossing matching problem, the input is aset of points in general position, and the goal is to match
points in a way that the edges between the matchedpairs do not cross. In the offline setting, it is rather easy
to solve the problem: one can sort all points by theirx-coordinate and match pairs of consecutive points. All
points, except possibly the last one, will be matched.
The running time of this algorithm is O(n log n), whichis asymptotically optimal [5]. Other variants of noncrossing matching have been studied in the offline set∗ Department of Computer Science,

University of Manitoba,
Winnipeg, Canada, shahin.kamali@umanitoba.ca† Department of Computer Science, University of Manitoba,
Winnipeg, Canada, nikbakhp@myumanitoba.ca‡ Department of Computer Science, University of Manitoba,
Winnipeg, Canada, sajadpoa@myumanitoba.ca

Arezoo Sajadpour‡ting (see [7]). For example, Aloupis et al. [1] considered
the computational complexity of finding non-crossing
matching of a set of points with a set of geometric objects that can be a line, a line segment, or a convex
polygon.
Bose et al. [3] studied the online variant of the noncrossing matching. Under this setting, the input is a setof n points in general position that appear in an online,
sequential manner. When a point x arrives, an online algorithm can match it with an existing unmatched pointy, provided that the edge between them does not crossprevious edges in the matching. Alternatively, the algorithm can leave the point unmatched to be matchedlater. In taking these decisions, the algorithm has no
information about the forthcoming points or the lengthof the input. The algorithm’s decisions are irrevocablein the sense that once a pair of points is matched, thatpair cannot subsequently be removed from the matching. The objective is to find a maximum matching.
Under a worst-case analysis, where an adversary generates the online sequence, it is not possible to match all
points. For example, consider an input that starts withtwo points x and y. If an online algorithm leaves thetwo points unmatched, then the adversary ends the sequence, and the matching is already sub-optimal. If thealgorithm matches x and y, then the adversary generates the next two points on the opposite sides of the line
between x and y, and the matching will be sub-optimalfor this input of length n = 4. Bose et al. [3] extended
this argument to show that in the worst case, no deterministic algorithm can match more than ⌈2n/3 − 1/3⌉
points. Meanwhile, they showed that any greedy algorithm matches at least ⌈2n/3 − 1/3⌉ points, and henceis optimal. An algorithm has the greedy property if itnever leaves a point x unmatched if there is a suitable
unmatched point y that x can be matched to (that is,
the edge between x and y does not cross existing edges
in the matching).
1.1

Contribution

We study randomized algorithms for the non-crossing
matching problem. As in [3], we study worst-case scenarios, where the input is generated adversarially. We
assume the adversary is oblivious to the random choices
made by the algorithm, but it is aware of how the algorithms works (that is, the code of the algorithm).
We present a randomized algorithm that matches at5th Iranian Conference on Computational Geometry

least ⌊235n/351 − 202/351⌋ ≈ 0.6695n points on expectation for any input of size n. This shows the advantage
of randomized algorithms over deterministic ones, whichmatch roughly 0.6̄n points in the worst case.
There are two main components in our randomized algorithm. First, the algorithm maintains a convex partitioning of the plane and matches two points only if they
appear in the same partition. This is followed by updating the partitioning by extending the edge between
the matched pair. This partitioning enables us to use
a simple inductive argument to analyze the algorithm.
Second, the algorithm deviates from the greedy strategy. In particular, the algorithm gives a chance for an
incoming point x to stay unmatched even if there are
one or two points in the same convex region that it canmatch. As we will see, this will be essential for any
improvement over deterministic algorithms.
2

A Randomized Online Algorithm

We present and analyze a randomized online algorithm
for the non-crossing matching problem. In what follows,
for any a ̸= b we use Lab to denote the line passing
through a and b, and Sab to denote the line segment
between a and b.
2.1

Algorithm’s description

The algorithm maintains a partitioning of the plane into
convex regions and matches points only if they belong
to the same region. In the beginning, there is only one
region that is formed by the entire plane. After four
points appear inside a convex region, one or two pairs of
points are matched, and the convex region is partitioned
into two or three convex regions by extending the line
segments passing through the matched pairs.
Let x, y, z, and w be the first four points inside aconvex region C in the same order. In what follows, we
describe how these four points are treated.
• Upon the arrival of x, there is no decision to make,given that there is no point inside C to be matchedwith x.
• Upon the arrival of y, it is matched with x witha probability of 1/2 and stays unmatched with aprobability of 1/2.
• Upon the arrival of z, if the pair (x, y) is alreadymatched, then there is no decision to make. Otherwise, z is matched with x with a probability of
1/3, with y with a probability of 1/3, and stays
unmatched with a probability of 1/3.
• Upon the arrival of w, there are two possibilities toconsider:– First, suppose a pair of points a, b ∈ {x, y, z}
is already matched, while a third point c ∈{x, y, z}/{a, b} is unmatched. If it is possible to match w with c (that is, Swc does notcross Sab ), then w is matched with c; otherwise, when Swc and Sab cross, there is no decision to make.
– Second, suppose no pair of the first threepoints are matched. Then w is matched witha point a ∈ {x, y, z} so that the two points
b, c ∈ {x, y, z}/{a} appear on different sidesof the line Law (if there is more than one such
point, w is matched with z).
After the arrival of four points inside C, either all
points are matched into two pairs, in which case we
say a “double-pair is realized”, or only two points arematched while the other two appear on different sidesof the matched pair, in which case we say a “single-pairis realized”. If a single-pair is realized, in this case, Cis partitioned into two convex regions. If a double-pairis realized, then algorithm extends the line segments
between the matched pairs until they hit the boundary of C or the (non-extended) segment between theother matched pair. This is followed by extending theline segment between the second pair until it hits theboundary of C or extended line that passes through thefirst matched pair. When a double-pair is realized, C ispartitioned into three convex regions.
Assume n ≥ 8. A single-pair is “good” if, after theappearance of all n points, both of the two regions resulted from extending the line segment of the matchingcontain at least 2 points, and it is “bad” otherwise. A
double-pair is said to be “good” if, after the appearanceof all n points, one of the three regions formed by extending the line segments of the two matchings is empty;
otherwise, it is “bad”. The presence of 2 or more than 2points, or no points in a region provides a possibility ofmatching all pairs; hence we assert that a single/double
pair is “good” or “bad” as specified above.
The following example illustrates the algorithm’s
steps. Consider an input formed by 10 points labeledfrom p1 to p10 in the order of their appearance, as depicted in Figure 1. The convex regions maintained by
the algorithm are highlighted in different colors. Initially, the entire plane is a convex region C0 , where point
p1 appears. Upon the arrival of p2 , the algorithm match
it with p1 with a probability of 1/2. Suppose (p1 , p2 ) arematched. Then, there is no decision to be made for p3 .
Upon the arrival of p4 , the line segments Sp1 p2 and Sp3 p4
do not cross. Therefore, p4 is matched with p3 . At thispoint, four points have appeared in C0 and a doublepair (p1 , p2 ) and (p3 , p4 ) has been realized. Therefore,
C0 is partitioned into three smaller convex regions C1 ,C2 , and C3 by extending Sp1 ,p2 and then Sp3 ,p4 (Figure 1a). Points p5 and p6 appear respectively in C3 andICCG 2022, Sharif UT, February 24, 2022

C1

C2

p3
p2

p4
p1

We use an inductive argument to prove f (n) ≤ cn +d where c = 116/351 ≈ 0.3304 and d = 32c − 10 =202/351 ≈ 0.5754. First, we apply Lemma 1 to establish
the base of induction in the following theorem.
Lemma 2 (appendix) For n ∈ [2, 7], it holds thatf (n) ≤ cn + d where c = 116/351 and d = 202/351.

C3(a) The state of the algorithm after processing p1 , . . . , p4 .
C1

p9

p3
p4
p1

C5

C2

p6
p2

• A good single-pair is realized with a probability ofat least 1/6

p10• A good double-pair is realized with a probability ofat least 1/6.

p5
p7
p8
C4

(b) The state of the algorithm after processing p1 , . . . , p10 .

Figure 1: One possible output of the algorithm when the
input is a sequence of 10 points labeled as p1 , . . . , p10 in
the order of their appearance.

C2 . Since these are the first points in their respective
regions, there is no decision to be made, and they stay
unmatched. Subsequently, p7 appears in C3 and thealgorithm matches with p5 with a probability of 1/2.
Suppose these two points are not matched. Upon thearrival of p8 in C3 , it is matched with p5 or p7 , eachwith a probability of 1/3, and is left unmatched with aprobability of 1/3. Suppose (p5 , p8 ) are matched. Next,
point p9 appears in C2 and is matched with p6 with aprobability of 1/2, and stays unmatched with a probability of 1/2. Suppose (p6 , p9 ) are matched. Finally,
point p10 appears on C3 . Given that the Sp7 p10 crosses
Sp5 p8 , there is no decision to be made, and p10 stays
unmatched. At this point, four points have appeared in
C3 , and a single-pair (p5 , p8 ) has been realized. Therefore, C3 is partitioned into two smaller convex regions
C4 and C5 by extending Sp5 ,p8 (Figure 1b).
2.2

Lemma 3 For n ≥ 8, after serving the first four points
inside a convex region, at least one of the followings
hold:

Algorithm’s analysis

Let f (n) denote the expected number of unmatchedpoints left by the algorithm when input is formed by nitems. We use an inductive argument to find an upperbound for f (n). First, we prove the following lemma.
The proof is based on case analysis, and can be foundin the appendix:
Lemma 1 (appendix) We have f (0) = 0, f (1) = 1,
f (2) = 1, f (3) = 4/3, f (4) ≤ 4/3, f (5) ≤ 5/3, f (6) ≤20/9, and f (7) ≤ 52/18.

Proof. (sketch) We provide a sketch of the proof here.
The detailed proof can be found in the appendix. Let
x, y, z, and w denote the first four points in the sameorder that they appear.
First, suppose the convex hull formed by the four
points is a triangle ∆. If w is inside ∆, then the pairs(x, y) and (w, z) form a double-pair that is realized witha probability of 1/2. If this is bad, then there should be
at least one future point on each side of the line passing
through (w, z), which means (w, z) is a good single-pair.
We note that the single-pair formed by (w, z) is realizedwith a probability of 1/6. Next, suppose w is a vertex of∆ and another point c ∈ {x, y, z} is inside ∆. Let a, b be
the other two points in {x, y, z}. Then, the pairs (a, b)and (c, w) form a double-pair which is realized with aprobability of at least 1/6. If this double-pair is not
good, then (w, z) is a good single-pair which is realizedwith a probability of 1/6.
Next, suppose the convex hull formed by the four
points is a quadrilateral and includes all of them as
its vertices. In this case, each of the two single-pairs
formed by the diagonals of the convex hull is realized
by a probability of at least 1/6. If both of these singlepairs are bad, then all the remaining points in the input sequence must appear in one of the quarter-planes
formed by extending these diagonals. Then, the doublepair formed by the pair of points on the boundary ofthe quarter-plane and the pair of points outside of thequarter-plain form a good double-pair. The probabilityof such a double-pair to be realized is at least 1/6. □We are now ready to prove the main result.
Theorem 4 There is a randomized algorithm that, for
any input formed by n ≥ 2 points, leaves at most cn + d
points unmatched, where c = 116/351 and d = 202/351.
Proof. We use an inductive argument to show that ouralgorithm satisfies the conditions specified in the theorem. For n ≤ 7, the claim holds by Lemma 1. Suppose

5th Iranian Conference on Computational Geometryn ≥ 8, and assume that for any m < n, it holds thatf (m) ≤ cm + d.
First, we claim that the number of unmatched points
is at most cn + d + (2 − 6c) when a bad single-pair isrealized, or a bad double-pair is realized after the first
four points appear. If a bad single-pair is realized, theneither (I) there is one point on one side of the matchedpair and n − 3 > 2 points on the other side, or (II)there is no point on one side of the matched pair andn − 2 > 2 points on the other side. For (I), by the
induction hypothesis, the number of unmatched points
on the side with n − 3 points will be at most f (n − 3) ≤cn − 3c + d. Therefore, the number of unmatched points
is at most f (n−3)+1 ≤ cn−3c+d+1 < cn+d+(2−6c).
The last inequality holds because c < 1/3. For (II), thenumber of unmatched points will be at most f (n − 2) ≤cn+d−2c < cn+d+(2−6c). If a double-pair is realized
which is not good, then one of the followings holds forthe three regions formed by extending the line segments
between the matched pairs:

at most 1/6((cn+d)+(d−2c))+5/6(cn+d+(2−6c)) =cn + d + 1/6(d − 32c + 10) = cn + d. The last equality
holds because d = 32c − 10.
Next, suppose case b) holds, that is, a good doublepair is realized with a probability of at least 1/6, which
implies a bad single-pair or double-pair is realized with aprobability of at most 5/6. In case the good double-pairis realized, by definition, at least one of the three convex regions formed by extending the double-pair will be
empty. For the other two regions, we have the following
cases:i) One region contains n − 6 points, and the other two
regions each contains one point. Note that n − 6 ≥2 since n ≥ 8. By the induction hypothesis, thenumber of unmatched points is at most 2 + f (n −6) = cn + d + (2 − 6c).

iii) Both regions include m ≥ 2 and n − m − 4 ≥ 2
points. In this case, the number of unmatchedpoints will be at most f (m) + f (n − m − 4) ≤cn + d + (d − 4c) < cn + d + (1 − 5c). The lastinequality holds because c + d < 1.

ii) One region contains m ≥ 2 points, another region
contains one point, and the third region containsn − m − 5 ≥ 2 points. The number of unmatchedpoints is at most f (m) + f (n − m − 5) + 1 ≤ cn −5c + 2d + 1 < cn + d + (2 − 6c). The last inequality
holds because c + d < 1.

Therefore, as long as the good double-pair is realized,
the number of unmatched points will be at most cn +d + (1 − 5c). On expectation, we can write f (n) ≤1/6((cn + d) + (1 − 5c)) + 5/6((cn + d) + (2 − 6c)) =cn + d + 1/6(11 − 35c) < cn + d. The last inequality
holds since c > 11/35.
□

iii) One region contains m1 ≥ 2 points, one region contains m2 ≥ 2 points, and the third region contains
m3 = n − m1 − m2 − 4 ≥ 2 points. The numberof unmatched points is at most f (m1 ) + f (m2 ) +f (m3 ) ≤ cn − 4c + 3d < cn + d + (2 − 6c). The lastinequality holds because c + d < 1.

References

In summary, if a bad single-pair or a bad double-pairis realized, the number of unmatched points is at mostcn + d + (2 − 6c), and the claim holds.
By Lemma 3, after the appearance of the first four
points, either a) a good pair or b) a good double-pair
can be realized with a probability of at least 1/6.
Suppose case a) holds, that is, a good single-pair isrealized with a probability of at least 1/6, which implies a bad single-pair or double-pair is realized with aprobability of at most 5/6. In case the good singlepair is realized, there will be m ≥ 2 points on one
side of the line segment connecting matched pair, andn − m − 2 ≥ 2 points on the other side. Therefore, the number of unmatched points will be at mostf (m) + f (n − m − 2) ≤ cn + 2d − 2c = (cn + d) + (d − 2c).
On expectation, the number of unmatched points will be[2] A. Banik, M. J. Katz, and M. Simakov. Bottleneck segment matching. In Proceedings of the 27th Canadian
Conference on Computational Geometry CCCG, 2015.

i) One region is empty, and the other contains n−4 ≥2 points, in which case the number of unmatchedpoints becomes f (n − 4) ≤ cn + d − 4c < cn + d +(1 − 5c). The last inequality holds because c < 1.
ii) One region contains a single point, and the otherone contains n − 5 ≥ 2 points. The number of
unmatched points will be at most f (n − 5) + 1 ≤cn + d + (1 − 5c).

[1] G. Aloupis, J. Cardinal, S. Collette, E. D. Demaine,
M. L. Demaine, M. Dulieu, R. F. Monroy, V. Hart,
F. Hurtado, S. Langerman, M. Saumell, C. Seara, and
P. Taslakian. Non-crossing matchings of points with geometric objects. Comput. Geom., 46(1):78–92, 2013.

[3] P. Bose, P. Carmi, S. Durocher, S. Kamali, and A. Sajadpour. Non-crossing matching of online points. In Proc.
32nd Canadian Conference on Computational Geometry(CCCG), 2020.
[4] A. Efrat, A. Itai, and M. J. Katz. Geometry helps inbottleneck matching and related problems. Algorithmica,
31(1):1–28, 2001.
[5] J. Erickson. https://mathoverflow.net/questions/86906.
https://mathoverflow.net/questions/86906. Accessed:
2020-05-03.
[6] A. Kaneko and M. Kano. Discrete geometry on red andblue points in the plane—a survey. Discrete & Computational Geometry, 25:551–570, 2003.

ICCG 2022, Sharif UT, February 24, 2022

[7] L. Lovász and M. Plummer. Matching Theory. AMS
Chelsea Publishing Series. North-Holland, 2009.
[8] P. M. Vaidya. Geometry helps in matching. SIAM J.
Comput., 18(6):1201–1225, 1989.

By Lemma 5, with a probability of at least 1/3, adouble-pair is realized, and with a probability of at
most 2/3, a single-pair is realized. Therefore, we canwrite f (5) ≤ 1/3 · 1 + 2/3 · 2 = 5/3.
• For n = 6, after the first four points appeared, either asingle-pair or a double-pair is realized:

Appendix
In order to prove Lemma 1, we first prove the following
lemma:
Lemma 5 After four points arrived in the convex region C,
with a probability of at least 1/3, a double-pair is realized,
and with a probability of at most 2/3, a single-pair is realized.
Proof. Let x, y, z, and w denote the four points in the sameorder they appear. There are two cases to consider:• Suppose Sxy crosses Swz . With a probability of 1/2, x
and y are not matched. After that, with a probability of
2/3, z is matched to x or y. Without loss of generality,
assume z is matched with x. Given that Sxy crosses
Swz , line segments Sxz and Syw will not cross, implyingthat w is matched to y, and a double-pair is realized.
So, with a probability of at least 1/2 · 2/3 = 1/3, allpoints are matched, and a double-pair is realized.
• Suppose Sxy does not cross Sxz . Then, (x, y) arematched with a probability of 1/2, and after that, (w, z)
are matched, and a double-pair is realized.
□
Using Lemma 5, we can prove Lemma 1:
Lemma 1 We have f (0) = 0, f (1) = 1, f (2) = 1, f (3) =4/3, f (4) ≤ 4/3, f (5) ≤ 5/3, f (6) ≤ 20/9, and f (7) ≤ 52/18.
Proof. Suppose n items appear in a convex region C. The
proof is trivial for n ≤ 2. In what follows, we prove thelemma for other values of n.
• For n = 3, it is possible that all points stay unmatched,which happens when the second point is not matchedwith the first one (with a probability of 1/2), and then
the third point is not matched with any of the firsttwo points (with a probability of 1/3). Therefore, witha probability of 1/6, all three points stay unmatched,and one point stays unmatched with a probability of
5/6. We can write f (3) = 1/6 · 3 + 5/6 · 1 = 4/3.
• For n = 4, using Lemma 5, we can write f (4) ≤ 1/3 ·0 + 2/3 · 2 = 4/3.
• For n = 5, after the first four points appeared, either asingle-pair or a double-pair is realized:– Suppose a single-pair is realized. Then, C is partitioned into two regions, one containing one point
and the other one containing two points. Therefore, it is expected that f (1) + f (2) = 2 points
stay unmatched.
– Suppose a double-pair is realized. Then, the first
four points are matched, and only the fifth pointstays unmatched.

– Suppose a single-pair is realized. Then, C is partitioned into two regions. Either (i) the fifth or
the sixth points appear on the same region, in
which case one region will have one point, andthe other one will have three points, or (ii) the
fifth and the sixth points appear in different regions, in which case each region contains twopoints. Therefore, it is expected that at mostmax{f (1) + f (3), f (2) + f (2)} = 7/3 points stay
unmatched.
– Suppose a double-pair is realized. Then, at most
2 points (the last two points) stay unmatched.
By Lemma 5, with a probability of at least 1/3, adouble-pair is realized, and with a probability of at
most 2/3, a single-pair is realized. Therefore, we canwrite f (6) ≤ 1/3 · 2 + 2/3 · 7/3 = 20/9.
• For n = 7, after the first four points appeared, either asingle-pair or a double-pair is realized:– Suppose a single-pair is realized. Then, C is partitioned into two regions. Either (i) the fifth, thesixth, and the seventh points all appear in thesame region, in which case one region has one
point, and the other one has four points (Figure 2a), or (ii) one of these points appear in one
region, and the other two appear in the other region, in which case one region contains two points,
and the other region contains three points (Figure 2b). Therefore, it is expected that at mostmax{f (1) + f (4), f (2) + f (3)} ≤ max{1 + 4/3, 1 +4/3} = 7/3 points stay unmatched.
– Suppose a double-pair is realized. Then, at
most three points stay unmatched, which happens
when any of the three regions formed by partitioning of the first four points includes a single point(see Figure 2c).
Unlike other cases, here, the expected number of unmatched points is larger when a double-pair is realized, and hence we cannot use Lemma 5. Instead,
we note that the probability of a single-pair being realized is at least 1/6 This is because a single-pair isrealized if either (i) the first two points are matchedwith a probability of 1/2, and the other two points appear on opposite sides of the line passing through thematched points, happening with a total probability of
1/2, (ii) the first two points are not matched with aprobability of 1/2, and the third point is matched toeither of the first points with a probability of 1/3, andthe fourth point appears on the side of the matchedline that the other unmatched point is not on, happening with a total probability of 1/6, or (iii) the
first three points stay unmatched with a probability of5th Iranian Conference on Computational Geometryd• A good single-pair is realized with a probability of atleast 1/6ca

• A good double-pair is realized with a probability of atleast 1/6.

b

Proof. Let x, y, z, and w denote the first four points in thesame order that they appear.
First, suppose the convex hull formed by the four points
is a triangle ∆ which includes the fourth point inside it. We
consider the following two cases:(a) The case where a single-pair is realized, and the last three points appear indifferent regions.
d• Assume w is the point that is inside ∆. Then the pairs(x, y) and (w, z) form a double-pair that is realized witha probability of 1/2. This is because the pair (x, y) ismatched with a probability of 1/2, and then the pair(w, z) is matched with a probability of 1. Meanwhile,(w, z) is a single-pair which is realized with a probability of 1/6. This is because, with a probability of 1/6,
the first three points stay unmatched, and then the algorithm matches w to z with a probability of 1. Now,
if the double pair formed by the pairs (x, y) and (w, z)
is bad, then there should be at least one future pointon each side of the line passing through (w, z), whichmeans (w, z) is a good single-pair (see Figure 3a).

c

a

b

(b) The case where a single-pair is realized, and the last three points appear indifferent regions.
c

a

b
d

(c) The case where a double-pair is realized, and the last three points appear indifferent regions.

Figure 2: The cases used in the calculation of f (7);a, b, c, d ∈ {x, y, z, w} where x, y, z, and w are the first
four points in the same order of their appearance.
1/2·1/3 = 1/6, and then the fourth point gets match tothe point that bisects the unmatched points, happening
with a total probability of 1/6. Therefore, we can write
f (7) ≤ 5/6 · 3 + 1/6 · 7/3 = 52/18 (see Figure 2).
□

Lemma 2 For n ∈ [2, 7], it holds that f (n) ≤ cn + d wherec = 116/351 and d = 202/351.
Proof. The proof follows from Lemma 1. For n = 2, wehave f (2) = 1 < 2c + d (since 2c + d > 1.2362). For n = 3,
we have f (3) = 4/3 = 3c + d (since 3c + d > 1.5669). For
n = 4, we have f (4) ≤ 4/3 < 4c + d (since 4c + d > 1.8974).
For n = 5, we have f (5) ≤ 5/3 < 5c + d (since 5c + d >2.2279). For n = 6, we have f (6) ≤ 20/9 < 6c + d (since
6c + d > 2.5584). For n = 7, we have f (7) ≤ 52/18 = 7c + d(note that 7c + d = 52/18).
□
Next, we provide the detailed proof of Lemma 3:
Lemma 3 For n ≥ 8, after serving the first four points
inside a convex region, at least one of the followings hold:• Assume w is a vertex of ∆ and another point c ∈{x, y, z} is inside ∆. Let a, b be the other two points
in {x, y, z}. Then, the pairs (a, b) and (c, w) form a
double-pair which is realized with a probability of atleast 1/6. This is because the pair (a, b) is matched witha probability of at least 1/6 (the pair (a, b) is matchedwith a probability of 1/2 if z ∈/ {a, b}, and with a probability of 1/6 if z ∈ {a, b}), and then w is matched withc with a probability of 1. Meanwhile, the pair (c, w) isa single-pair which is realized with a probability of 1/6.
Similar to the previous case, if the double pair formedby the pairs (a, b) and (c, w) is bad, then there should
be at least one future point on each side of (a, b), whichmeans (a, b) is a good single-pair (see Figure 3b).
Next, suppose the convex hull formed by the four points
is a quadrilateral and includes all of them. Consider thetwo single-pairs formed by the diagonals of the convex hull.
Any of these pairs can be realized with a probability of atleast 1/6. Specifically, the diagonal involving w is realized
when no pair of points from {x, y, z} are matched, whichtakes place with a probability of 1/6. The other diagonal
is either between x and y, which is realized with a probability of 1/2, or between z and a ∈ {x, y}, which is realizedwith a probability of 1/6. Therefore, if any of the two diagonal forms a good single-pair, the statement of the lemma
holds, and we are done (see Figure 3c). If none of the two
diagonals is good, then all the remaining points in the input
sequence should appear in one of the quarter-planes formedby extending these diagonals (see Figure 3d). Then, thedouble-pair formed by the pair of points on the boundaryof the quarter-plane (points b and c in Figure 3d) and thepair of points outside of the quarter-plain (points w and a in
Figure 3d) form a good double-pair. The probability of sucha double-pair to be realized is at least 1/6. This is because
one of the pairs in the double-pair involves two of the first
three points. If these points are (x, y), the double-pair is

ICCG 2022, Sharif UT, February 24, 2022

w

z

w

x

y

c

a

(a)

b

(b)
c

c
w

w

a

b

(c)

a

b

(d)

Figure 3: An illustration of the proof of Lemma 3. (a)when w is inside the triangle ∆, either the single-pairformed by (w, z) is a good single-pair, or the doublepair formed by (x, y), (w, z) is a good double-pair. (b)when c ∈ {x, y, z} is inside the triangle ∆, either the
double pair formed by (a, b), (w, c) is a good doublepair, or the single-pair formed by (w, c) is a good singlepair. (c) the case when at least one of the diagonals of
the convex hull formed by the four points (here (w, b))forms a good single-pair (d) when none of the singlepairs formed by the diagonals of the convex hull are
good, all remaining points appear in one of the quarterplanes formed by extending these diagonals; therefore,
the pair of points on the boundary of the quarter-plane(here (b, c)) and the pair of points outside the quarterplanes (here (w, a)) form a good double-pair.

realized with a probability of 1/2; otherwise, it is realizedwith a probability of 1/6.
□