Algorithms and data structures in computational geometry

This thesis pertains to three mostly unrelated topics in computational geometry.; I. Generalizations of the usual median to two and more dimensions. Given a set of n points in $Rd$, the Tukey depth of some particular point p is the minimum number of points contained in any halfspace containing p. Given a set of n hyperplanes in $Rd$, the hyperplane depth of some point p is the minimum number of hyperplanes intersecting any ray from p to infinity. For each of these depths, a median is a point of maximal depth. We study the computational problem of finding a median. We prove an Ω( n log n) lower bound for both of these problems. We also present an optimal O(n log n) algorithm for computing the depth of the deepest point inside any cell of an arrangement of n lines in the plane, and a O(n(log n)3) time algorithm for finding a Tukey median in the plane. These algorithms use several new tools for arrangements of lines that should be of independent interest.; II. Data structures can play a crucial role in geometric algorithms. We present a data structure for maintaining the Minimum Clique Cover and Maximum Independent Set of a circular-arc graph. These can be maintained during the interchange of adjacent arc endpoints, in O(log n) amortized time per interchange. The data structure extends the dynamic tree structure of Sleator and Tarjan [54] so that cutting and linking O(n) subtrees can be done in one O(log n) time operation. We then give as an application and motivation for our data structure, a O(n4 log n) algorithm for a generalized shooter location problem [60]. The best previous algorithm has complexity O(n5), and was for a restricted version of the problem [10].; III. Given a non-convex simple polygon, an interesting question is whether it is possible to construct a data structure which, after initial preprocessing can answer halfspace area queries (i.e. determine the area of the portion of the polygon above a line) in o( n) time. We answer this question negatively, but present an efficient algorithm if many queries are asked at the same time.