Convex Hull for Probabilistic Points

We introduce an O(n log n) time algorithm for the convex hull problem on points with locations determined by a continuous probability distribution. Such probabilistic points are common in applied settings such as location-based services using machine learning determined locations. Our algorithm finds the convex hull of such points to precision within some expected correctness determined by a user-given confidence value p. In order to precisely explain how correct the resulting structure is, we introduce a new certificate error model for calculating and understanding approximate geometric error based on the fundamental properties of a geometric structure. We show that this new error model implies correctness under a robust statistical error model, in which each point lies within the hull with probability at least p, for the convex hull problem. We additionally show that the error model that we introduce, which is based on certificates of the type used in kinetic data structures (KDS), allows for a translation of the KDS framework to this probabilistic points setting. We thus introduce a framework for calculating and maintaining geometric structures on moving objects, even when the precise location of those objects is known only probabilistically. Our framework maintains the geometric structures to within approximate correctness based on our new certificate error model. We show that, under our translation, any existing KDS is approximately correct and is efficient or close to efficient.