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

https://hal.inria.fr/hal-01197244
Contributor : Coordination Episciences Iam <>
Submitted on : Friday, September 11, 2015 - 12:55:07 PM
Last modification on : Wednesday, February 27, 2019 - 11:08:02 AM
Long-term archiving on: : Tuesday, December 29, 2015 - 12:36:09 AM

File

dmAQ0114.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01197244, version 1

Collections

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. ⟨hal-01197244⟩

Share

Metrics

Record views

325

Files downloads

565