Conference proceeding
Approximate shape fitting via linearization
Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pp.66-73
2001
DOI: 10.1109/SFCS.2001.959881
Abstract
Shape fitting is a fundamental optimization problem in computer science. The authors present a general and unified technique for solving a certain family of such problems. Given a point set P in R/sup d/, this technique can be used to /spl epsi/-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//spl epsi//sup c/), where c is a constant that depends on the problem at hand. Our new general technique enables us to solve those problems without resorting to a careful and painful case by case analysis, as was previously done for those problems. Furthermore, for several of those problems our results are considerably simpler and faster than what was previously known. In particular, for the minimum width cylindrical shell problem, our solution is the first algorithm whose running time is subquadratic in n. (In fact we get running time linear in n.).
Details
- Title: Subtitle
- Approximate shape fitting via linearization
- Creators
- S Har-Peled - University of Illinois Urbana-ChampaignK.R Varadarajan - University of Iowa
- Resource Type
- Conference proceeding
- Publication Details
- Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pp.66-73
- Publisher
- IEEE
- DOI
- 10.1109/SFCS.2001.959881
- ISSN
- 1552-5244
- eISSN
- 2168-9253
- Language
- English
- Date published
- 2001
- Academic Unit
- Computer Science
- Record Identifier
- 9984259417202771
Metrics
3 Record Views