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 sampling
Authors: Daria Schymura
NULL
Daria Schymura
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)
Averkov, Gennadiy; Bianchi, Gabriele, 2014, Covariograms Generated By Valuations, International Mathematics Research Notices, 2015, 19, pp. 92779329, 10.1093/imrn/rnu219, http://arxiv.org/pdf/1307.1529.
Bianchi, Gabriele, 2016, The Covariogram And Fourier–Laplace Transform In ℂN, Proceedings Of The London Mathematical Society, 113, 1, pp. 123, 10.1112/plms/pdw020, http://arxiv.org/pdf/1312.7816.