2012/05/01 by Allan Grønlund Jørgensen, Jorgensen, Allan, Maarten Löffler +3
Computer Science · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Management and Algorithms #FOS: Computer and information sciences #Image and Object Detection Techniques
paper · pdf · doi:10.48550/arxiv.1205.0273
openalex publication_date 2012/05/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study computing geometric problems on uncertain points. An uncertain point is a point that does not have a fixed location, but rather is described by a probability distribution. When these probability distributions are restricted to a finite number of locations, the points are called indecisive points. In particular, we focus on geometric shape-fitting problems and on building compact distributions to describe how the solutions to these problems vary with respect to the uncertainty in the points. Our main results are: (1) a simple and efficient randomized approximation algorithm for calculating the distribution of any statistic on uncertain data sets; (2) a polynomial, deterministic and exact algorithm for computing the distribution of answers for any LP-type problem on an indecisive point set; and (3) the development of shape inclusion probability (SIP) functions which captures the ambient distribution of shapes fit to uncertain or indecisive point sets and are admissible to the two algorithmic constructions.