Convex Hull Simplification and Geometric Hardness

As data can often be viewed as geometric points, using geometric algorithms for extracting properties of the data is natural. Relevant examples include simplifying the structure of the data or generating a clustering of the data. This dissertation studies two problems concerning geometric data. The first is the problem of simplifying convex hulls by selecting a subset of the original point set such that its convex hull minimizes certain error functions. The error measures are defined in terms of distances between the selected convex hull and the full set of points. In particular, the focus in this dissertation is on the maximum distance, and the sum of distances. Results for these measures include exact algorithms in two dimensions and hardness results in higher dimensions. The second problem considered in this dissertation is the problem of k-center clustering of disjoint convex objects. The results include approximation algorithm for disks, and hardness results for line segments, unit disks, and axis aligned unit squares.