Abstract

This thesis explores several problems in computational geometry and online algorithms,
focusing on efficient algorithms for geometric optimization and real-time decision-making. We
begin by addressing the offline computational geometry problem of the Maximum Weighted
Convex Polytope (MWCP), followed by two online algorithmic problems: Online Non-Crossing
Matching and Online Interval Scheduling.
In the MWCP problem, the goal is to find a convex polytope within a set of n weighted (positive
and negative) points in R^d that maximizes the total weight of points inside or on the boundary.
We present a new simple algorithm for the two-dimensional case, achieving the same time
complexity of O(n^3) as previous methods. We also prove that MWCP is NP-hard in dimensions
three or higher, even when weights are restricted to +1 and -1, and that in dimensions four or
higher, the problem is NP-hard to approximate within a factor of n^{1/2-epsilon}.
We next focus on the Online Non-Crossing Matching problem, where points arrive sequentially
in the plane and must be irrevocably matched to previously arrived points such that the resulting
matched pairs form non-crossing line segments. We introduce the weighted version of this
problem, aiming to maximize the total weight of matched pairs. We show that deterministic
algorithms can have arbitrarily bad competitive ratios due to adversarial weight assignments. To
address this, we consider weights within the range [1, U] and provide an algorithm with a
competitive ratio of Omega (2^{-2 sqrt{ log U }}), along with an upper bound of O(2^{-sqrt{log
U}}) for any deterministic algorithm. In the setting that allows revoking, we develop an algorithm
that achieves a competitive ratio of approximately 0.28, and prove that no deterministic
algorithm can exceed a competitive ratio of 2/3, even in the unweighted case. Additionally, we
propose a randomized algorithm with a competitive ratio of 1/3, and show that no randomized
algorithm can surpass a competitive ratio of 8/9 in the unweighted case.
We also study the advice complexity of this problem. We establish a lower bound of (n/3) - 1 on
the advice complexity and provide an algorithm that uses approximately 2n bits of advice,
matching log C_n, where C_n is the n th Catalan number. Furthermore, we derive a lower
bound on the advice complexity required to achieve a competitive ratio in (16/17, 1). In the
bichromatic version of this problem, where a set of n blue points are given offline and red points
arrive online to be matched only to blue points, we correct previous errors in the literature and
establish a lower bound of log C_n on the advice complexity. We also present an algorithm that
uses log C_n bits of advice when points arrive in convex position.
In the final part, we consider the Online Interval Selection problem when the interval graph of
the input is a simple path, allowing revoking of previous decisions. We show that under the
random-order model, a deterministic memoryless algorithm achieves a competitive ratio of
approximately 0.78. We also established an upper bound of 3/4 for any deterministic revoking

algorithm on a simple chain in the adversarial model, and a lower bound of n/4 for the advice
complexity of Online Interval Selection, marking the first lower bound for this problem.
Throughout this work, we develop novel algorithmic techniques, establish tight complexity
bounds, and provide new insights into advice complexity for key problems in computational
geometry and online algorithms. These contributions aim to advance the theoretical foundations
of these fields and have potential applications in real-time systems and geometric data analysis.