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}
NULL
Daria Schymura
1 Institut für Informatik [Berlin]
We give simple probabilistic algorithms that approximately maximize the volume of overlap of two solid, i.e. fulldimensional, shapes under translations and rigid motions. The shapes are subsets of $ℝ^d$ where $d≥ 2$. The algorithms approximate with respect to an prespecified 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)