# 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.
Keywords :
Document type :
Conference papers
Domain :

Cited literature [17 references]

https://hal.inria.fr/hal-01197244
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

### File

dmAQ0114.pdf
Publisher files allowed on an open archive

### Citation

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