Approximating Extent Measure of Points

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

This is a merge of two papers: "Approximate Shape fitting via Linearization ", with K.R. Varadarajan, and "Maintaining the Approximate Extent Measures of Moving Points ", with P.K. Agarwal.

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.

Postscript file
PDF

Bibtex:

@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}
}

Last modified: Mon Aug 2 17:21:27 CDT 2004