APPROXIMATING THE DIAMETER, WIDTH, SMALLEST ENCLOSING CYLINDER, AND MINIMUM-WIDTH ANNULUS
Author:
- 1 February 2002
- journal article
- research article
- Published by World Scientific Pub Co Pte Ltd in International Journal of Computational Geometry & Applications
- Vol. 12 (01n02) , 67-85
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).Keywords
This publication has 28 references indexed in Scilit:
- Smallest Enclosing CylindersAlgorithmica, 2000
- On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed DimensionJournal of Algorithms, 1996
- A deterministic algorithm for the three-dimensional diameter problemComputational Geometry, 1996
- Las Vegas algorithms for linear and integer programming when the dimension is smallJournal of the ACM, 1995
- Applications of Parametric Searching in Geometric OptimizationJournal of Algorithms, 1994
- Linear Optimization QueriesJournal of Algorithms, 1993
- Reporting points in halfspacesComputational Geometry, 1992
- Farthest neighbors, maximum spanning trees and related problems in higher dimensionsComputational Geometry, 1992
- Linear Programming in Linear Time When the Dimension Is FixedJournal of the ACM, 1984
- A lower bound for the volume of strictly convex bodies with many boundary lattice pointsTransactions of the American Mathematical Society, 1963