## Non-crossing matching of online points

##### Abstract

In this thesis, we consider the non-crossing matching problem in the online setting.
In the monochromatic setting, a sequence of n points in general position in the plane
is revealed in an online manner. The goal is to create a maximum matching of these
points such that the line segments connecting pairs of matched points do not cross.
The problem is online in the sense that the decision to match each arriving point is
irrevocable and should be taken without prior knowledge about forthcoming points.
The bichromatic setting is defined similarly, except that half of the points are red
and the rest are blue. Each matched pair then consists of one red point and one blue
point.
In a deterministic setting, where randomization is not allowed, we show that a
simple greedy algorithm matches roughly 2n/3 points in the monochromatic case,
which is the best that any deterministic algorithm can achieve in the worst-case
scenario. For the bichromatic variant, we prove that for every deterministic algorithm
Alg there is a set of n/2 red points and n/2 blue points such that Alg matches at
most O(log n) points, and there exist algorithms that match Ω(log n) points for
any set of n/2 red points and n/2 blue points. We also study the problem under the
advice model, where the online algorithm receives some bits of advice about the input
sequence. We prove upper and lower bounds for the number of advice bits sufficient
and necessary to match all points.
We show that randomization helps in the monochromatic matching of the problem.
That is, we introduce an algorithm that matches roughly 235n/351 (> n/3) points on
expectation, which is an improvement over what deterministic algorithms can achieve.
We also prove a lower bound that shows a linear number of points stay unmatched by
any randomized algorithm. More precisely, we show that any randomized algorithm
is expected to leave at least 0.0738n points unmatched in the worst-case scenarios.
Finally, we provide experimental results for the typical performance of online
algorithms. We report the number of unmatched points when the coordinates of the
input points are independently and identically distributed random variables.