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.