Algorithms and Data Structures for Geometric Object Approximation Problems

The topic of geometric object approximation focuses on computing structurally or geometrically simpler objects to approximate an input complex object. This is a fundamental and important research topic in computational geometry and has many applications. In this dissertation, we study a number of geometric approximation problems. Specifically, we study the problems of approximating a set of points in the plane by a functional curve as well as other variants which include the weighted points, in the presence of outliers, and the 3-D extensions. Further, we develop a new type of outlier-handling algorithms, which not only detect the outliers but also accommodate their impact. In addition, we study the problems of approximating a piecewise linear nonnegative functional curve in the plane by a set of 'simpler' nonnegative curves, which can be a nonincreasing curve and a nondecreasing curve, or a set of unimodal curves, or a piecewise linear curve with fewer peaks. Finally, we study the obnoxious line problem, which can be viewed as a dual version of the geometric approximation problem. Given a set of polygons in the plane, the goal of the obnoxious line problem is to compute a line which maximizes its minimum distance to all polygons and the line is required to intersect the convex hull of all polygons. All these problems are motivated by real applications. We develop efficient exact algorithms for most of the problems. Some of our algorithms are first-known while others improve the previous work in terms of the running time and space. Our algorithms are based on combinations of interesting algorithmic techniques, geometric observations, problem modeling and careful analysis. In addition, for solving these problems, we develop a number of new data structures, e.g., vertical hull width query, 2-D sublist query, 3-D sublist query, q-range-minimia, simplicial thickness query, etc., which are interesting in their own rights and can easily find other applications.