Convex Hull for Probabilistic Points

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 correctne...

Full description

Saved in:
Bibliographic Details
Main Authors: Atalay, F. Betul, Friedler, Sorelle A., Xu, Dianna
Format: Conference Proceeding
Language:English
Subjects:
Adaptation models
approximately correct
Approximation algorithms
Computational modeling
convex hull
Probabilistic logic
probabilistic points
Probability density function
Probability distribution
Robustness
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 phi. 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 φ, for the convex hull problem.
ISSN:2377-5416
DOI:10.1109/SIBGRAPI.2016.016