Tel-Aviv University - Computer Science Colloquium
Sunday, June 6, 14:15-15:15
at 14:00 In this talk, we will present efficient approximation algorithms for the following problem:
Let S be a set of n points in \Re^d. Estimate the ``roundness'' of S by computing the width W(S) of the thinnest spherical shell (or annulus in \Re^2) that contains S.
The main motivation for computing a minimum-width shell or annulus comes from metrology. For example, the circularity of a two-dimensional object O in the plane is measured by sampling a set S of points on the surface of O (e.g. using coordinate measurement machines) and computing the width of the thinnest shell containing S. Motivated by this and other applications, the problem of computing A(S) in the plane has been studied extensively.
We will present two algorithms for this problem:
(i) For the planar case, we can compute, for any given parameter eps > 0, an annulus containing S whose width is at most (1 + eps)W(S), in time O(n log(n) + n/eps^2).
(ii) For d >= 3, given a parameter eps > 0, we can compute a shell containing S of width at most (1+eps)W(S) in time O( n/(eps^d) log( Diameter(S) / ( W(S) eps ) ) ).
Previous to this work, no efficient algorithm that achieves an epsilon-approximation of the width of the optimal solution was known.
Joint works with P. Agarwal, B. Aronov, and M. Sharir
For colloquium schedule, see http://www.math.tau.ac.il/~matias/colloq.html