Approximate Centerpoints with Proofs
Presented at the Symposium on Computational Geometry, 2009, in Aarhus, Denmark.
We show how to derandomize the Iterated-Radon algorithm to achieve the first deterministic algorithm for computing approximate centerpoints that runs in time subexponential in the dimension. The algorithm also returns a polynomial-time checkable proof of the quality of the returned centerpoint.