About the error term for best approximation with respect to the Hausdorff related metrics

Abstract

Let M be a convex body with C + 3 boundary in ℝ d , d ≥ 3, and consider a polytope P n (or P (n) ) with at most n vertices (at most n facets) minimizing the Hausdorff distance from M. It has long been known that as n tends to infinity, there exist asymptotic formulae of order n −2/(d-1) for the Hausdorff distances δH(P n , M) and δH(P (n) , M). In this paper a bound of order n −5/(2(d-1)) is given for the error of the asymptotic formulae. This bound is clearly not the best possible, and Gruber[9] conjectured that if the boundary of M is sufficiently smooth, then there exist asymptotic expansions for δH(P n , M) and δH(P (n) , M). With the help of quasiconformal mappings, we show for the three-dimensional unit ball that the error is at least f (n) · n −2 where f (n) tends to infinity. Therefore in this case, no asymptotic expansion exists in terms of n −2/(d-1) = n −1.

Locations

• Discrete & Computational Geometry - View - PDF