## Abstract

Let S be a set of n points in ℝ^{d}. The "roundness" of S can be measured by computing the width ωz.ast; = ω*(S) of the thinnest spherical shell (or annulus in ℝ^{2}) that contains S. This paper contains two main results related to computing an approximation of ω*: (i) For d = 2, we can compute in O(n log n) time an annulus containing S whose width is at most 2ω*(S). We extend this algorithm, so that, for any given parameter ε > 0, an annulus containing S whose width is at most (1 + ε)ω* is computed in time O(n log n + n/ε^{2}). (ii) For d ≥ 3, given a parameter ε > 0, we can compute a shell containing S of width at most (1 + ε)ω* either in time O((n/ε^{d}) log(Δ/ω*ε)) or in time O((n/ε^{d-2})(log n + 1/ε) log(Δ/ω*ε)), where Δ is the diameter of S.

Original language | English (US) |
---|---|

Pages (from-to) | 687-705 |

Number of pages | 19 |

Journal | Discrete and Computational Geometry |

Volume | 24 |

Issue number | 4 |

DOIs | |

State | Published - Dec 2000 |

Externally published | Yes |

## ASJC Scopus subject areas

- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics