2014/12/02 by F. Betul Atalay, Sorelle A. Friedler, Atalay, F. Betul +3
Computer Science · Engineering · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Indoor and Outdoor Localization Technologies #Robotics and Sensor-Based Localization
paper · pdf · doi:10.48550/arxiv.1412.1039
openalex publication_date 2014/12/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We analyze the correctness of an O(n log n) time divide-and-conquer algorithm for the convex hull problem when each input point is a location determined by a normal distribution. We show that the algorithm finds the convex hull of such probabilistic points to precision within some expected correctness determined by a user-given confidence value. 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 that of the user-given confidence value, for the convex hull problem.