Daria Schymura - Matching solid shapes in arbitrary dimension via random sampling

dmtcs:2992 - Discrete Mathematics & Theoretical Computer Science, January 1, 2012, DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12) - https://doi.org/10.46298/dmtcs.2992
Matching solid shapes in arbitrary dimension via random samplingArticle

Authors: Daria Schymura 1

  • 1 Institut für Informatik [Berlin]

We give simple probabilistic algorithms that approximately maximize the volume of overlap of two solid, i.e. full-dimensional, shapes under translations and rigid motions. The shapes are subsets of $ℝ^d$ where $d≥ 2$. The algorithms approximate with respect to an pre-specified additive error and succeed with high probability. Apart from measurability assumptions, we only require that points from the shapes can be generated uniformly at random. An important example are shapes given as finite unions of simplices that have pairwise disjoint interiors.


Volume: DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)
Section: Proceedings
Published on: January 1, 2012
Imported on: January 31, 2017
Keywords: shape matching,randomized algorithms,computational geometry,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG]

2 Documents citing this article

Consultation statistics

This page has been seen 217 times.
This article's PDF has been downloaded 148 times.