  The computation of (i) $\varepsilon$-kernels, (ii) approximate diameter, and
(iii) approximate bichromatic closest pair are fundamental problems in
geometric approximation. In this paper, we describe new algorithms that offer
significant improvements to their running times. In each case the input is a
set of $n$ points in $R^d$ for a constant dimension $d \geq 3$ and an
approximation parameter $\varepsilon > 0$. We reduce the respective running
times (i) from $O((n + 1/\varepsilon^{d-2})\log(1/\varepsilon))$ to $O(n
\log(1/\varepsilon) + 1/\varepsilon^{(d-1)/2+\alpha})$, (ii) from $O((n +
1/\varepsilon^{d-2})\log(1/\varepsilon))$ to $O(n \log(1/\varepsilon) +
1/\varepsilon^{(d-1)/2+\alpha})$, and (iii) from $O(n / \varepsilon^{d/3})$ to
$O(n / \varepsilon^{d/4+\alpha}),$ for an arbitrarily small constant $\alpha >
0$. Result (i) is nearly optimal since the size of the output
$\varepsilon$-kernel is $\Theta(1/\varepsilon^{(d-1)/2})$ in the worst case.
  These results are all based on an efficient decomposition of a convex body
using a hierarchy of Macbeath regions, and contrast to previous solutions that
decompose space using quadtrees and grids. By further application of these
techniques, we also show that it is possible to obtain near-optimal
preprocessing time for the most efficient data structures to approximately
answer queries for (iv) nearest-neighbor searching, (v) directional width, and
(vi) polytope membership.
