Pankaj K. Agarwal and
Sariel Har-Peled and
Kasturi R. Varadarajan

Shape fitting is an important optimization problem in computational
geometry. We present a general technique for solving such problems:
For a given a point set P in R^{d}, this
technique can be used to µ-approximate:(i) the min-width
annulus and shell that contains P,(ii) minimum width cylindrical
shell containing P,(iii) diameter, width, minimum volume
bounding box of P, and(iv) all the previous measures for
the case the points are moving. The running time of the resulting
algorithms is O(n + 1/µ^{c}), where c
is a constant that depends on the problem at hand.

Our
new general technique enable us to solve those problems in a
plug and play manner, and for several of those problems our results
are considerably faster than what was previously known.

@article{ahv-aemp-04,
author = {P. K. Agarwal and S. {Har-Peled} and
K. R. Varadarajan},
title = {Approximating extent measures of points},
journal = {J. ACM},
volume = {51},
number = {4},
year = {2004},
issn = {0004-5411},
pages = {606--635},
doi = {http://doi.acm.org/10.1145/1008731.1008736},
publisher = {ACM Press},
}

Proceedings version

@string{FOCS_2001 = "Proc. 42nd Annu. IEEE Sympos. Found. Comput. Sci."}
@inproceedings{hv-asfl-01,
author = {S.~{Har-Peled} and K.R.~Varadarajan},
title = {Approximate Shape Fitting via Linearization},
booktitle = FOCS_2001,
year = 2001,
pages = "66--73"
}
@string{SODA12 = "Proc. 12th ACM-SIAM Sympos. Discrete Algorithms"}
@InProceedings{ah-maemm-01,
author = {P.K.~Agarwal and S.~Har-Peled},
title = {Maintaining the Approximate Extent Measures of Moving Points},
booktitle = SODA12,
year = 2001,
pages = {148--157}
}