ISSN:
1432-0444
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract. Let S be a set of n points in \re d . The ``roundness'' of S can be measured by computing the width ω * =ω * (S) of the thinnest spherical shell (or annulus in \re 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 \geq 3 , given a parameter ε 〉 0 , we can compute a shell containing S of width at most (1+ε)ω * either in time O ( n / ε d ) log ( \Delata / ω * ε ) or in time O ( n / ε d-2 ) log n + 1 / εlog \Delata / ω * ε , where Δ is the diameter of S .
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/s004540010062
