Abstract
We study (1 + ε)-factor approximation algorithms for several well-known optimization problems on a given n-point set: (a) diameter, (b) width, (c) smallest enclosing cylinder, and (d) minimum-width annulus. Among our results are new simple algorithms for (a) and (c) with an improved dependence of the running time on ε, as well as the first linear-time approximation algorithm for (d) in any fixed dimension. All four problems can be solved within a time bound of the form O(n + ε-c) or O(n log(1/ε) + ε-c).
| Original language | English (US) |
|---|---|
| Pages (from-to) | 67-85 |
| Number of pages | 19 |
| Journal | International Journal of Computational Geometry and Applications |
| Volume | 12 |
| Issue number | 1-2 |
| DOIs | |
| State | Published - 2002 |
| Externally published | Yes |
Keywords
- Approximation algorithms
- Diameter
- Geometric optimization
- Roundness
- Width
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Computational Theory and Mathematics
- Computational Mathematics
- Applied Mathematics