Skip to Main content Skip to Navigation
Conference papers

Matching solid shapes in arbitrary dimension via random sampling

Abstract : 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.
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Friday, September 11, 2015 - 12:55:07 PM
Last modification on : Thursday, January 6, 2022 - 12:14:04 PM
Long-term archiving on: : Tuesday, December 29, 2015 - 12:36:09 AM


Publisher files allowed on an open archive




Daria Schymura. Matching solid shapes in arbitrary dimension via random sampling. 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'12), 2012, Montreal, Canada. pp.167-178, ⟨10.46298/dmtcs.2992⟩. ⟨hal-01197244⟩



Record views


Files downloads