Shape Fitting on Point Sets with Probability Distributions

DOI10.1007/978-3-642-04128-0_29MaRDI QIDQ3639256zbMATH OpenOpenAlexFDO

Authors Maarten Löffler, Jeff M. Phillips

Publication date 29 October 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0812.2967

Mathematics Subject Classification ID

General topics in the theory of data (68P01) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Abstract: A typical computational geometry problem begins: Consider a set P of n points in R^d. However, many applications today work with input that is not precisely known, for example when the data is sensed and has some known error model. What if we do not know the set P exactly, but rather we have a probability distribution mu_p governing the location of each point p in P? Consider a set of (non-fixed) points P, and let mu_P be the probability distribution of this set. We study several measures (e.g. the radius of the smallest enclosing ball, or the area of the smallest enclosing box) with respect to mu_P. The solutions to these problems do not, as in the traditional case, consist of a single answer, but rather a distribution of answers. We describe several data structures that approximate distributions of answers for shape fitting problems. We provide simple and efficient randomized algorithms for computing all of these data structures, which are easy to implement and practical. We provide some experimental results to assert this. We also provide more involved deterministic algorithms for some of these data structures that run in time polynomial in n and 1/eps, where eps is the approximation factor.

Recommendations

• scientific article; zbMATH DE number 841447
• On the sensitivity of shape fitting problems
• SURFACE FITTING TO RANDOM DATA VIA CONSTRAINED SHAPING
• Statistical shape theory
• scientific article; zbMATH DE number 2147957
• scientific article; zbMATH DE number 5149735
• Shape classification based on interpoint distance distributions
• scientific article; zbMATH DE number 3967549
• Probabilistic Models for Shapes as Continuous Curves

Cited in

(14)

• Fast approximation of betweenness centrality through sampling
• High-dimensional shape fitting in linear time
• Percolation centrality via Rademacher Complexity
• Active set algorithms for estimating shape-constrained density ratios
• Region-based approximation of probability distributions (for visibility between imprecise points among obstacles)
• Core-sets: updated survey
• scientific article; zbMATH DE number 5149735 (Why is no real title available?)
• Approximating the Expected Values for Combinatorial Optimization Problems over Stochastic Points
• (Approximate) uncertain skylines
• Computing the Expected Value and Variance of Geometric Measures
• -kernel coresets for stochastic points
• scientific article; zbMATH DE number 841447 (Why is no real title available?)
• Approximating the distribution of the median and other robust estimators on uncertain data
• A Range Space with Constant VC Dimension for All-pairs Shortest Paths in Graphs

This page was built for publication: Shape Fitting on Point Sets with Probability Distributions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3639256)