Near-Optimal $\epsilon$-Kernel Construction and Related Problems

Sunil Arya, Guilherme D. da Fonseca, David M. Mount

The computation of (i) $\epsilon$-kernels, (ii) approximate diameter, and (iii) approximate bichromatic closest pair are fundamental problems in geometric approximation. In this…