Uncertain Inputs for Convex Hulls and Clustering

Geometric algorithms and inputs have received an increasing amount of attention with the explosion of data and computing challenges that arise from real world applications. This real world data is often uncertain in nature, either in the location or the existence of the data points. However, many classical computational geometry algorithms assume inputs to be precise. Thus the inherent presence of uncertainty in real data motivates the further exploration of classical geometric problems, though modeled to include uncertain inputs. This dissertation considers two of the most fundamental computational geometry problems, namely convex hulls and clustering, when the inputs are uncertain. We consider two different ways to model uncertainty: (i) uncertainty on location, where an uncertain point set is a collection of compact regions in the plane, and (ii) a probabilistic framework to model the existence of each point from the input point set. First, we study the complexity of the convex hull when the uncertain input points are modeled as a set of compact subsets, namely line segments. Here we seek the realization of the points whose convex hull has the fewest number of vertices. Next, we explore the classic k-center clustering problem for when the uncertain input points are a set of convex objects, for which we present several results. Finally, the last part of this dissertation concerns the k-center clustering problem with probabilistic centers, where each cluster center has a probability of failure. In presenting geometric properties, algorithms, and hardness results for convex hulls and clustering, this dissertation aims to give a better understanding to fundamental geometric problems with uncertain inputs.