DMTCS Proceedings, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)

Font Size:  Small  Medium  Large

Matching solid shapes in arbitrary dimension via random sampling

Daria Schymura

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.

Full Text: PostScript PDF

Valid XHTML 1.0 Transitional