Approximate centerpoints with proofs (Q991175)

The first deterministic algorithm -- the so called iterated-Tverberg algorithm -- is presented. The iterated-Tverberg algorithm is a derandomization of the iterated-Radon algorithm that deterministically computes an approximate center point of a set of points in a \(d\)-dimensional space with running time sub-exponential in \(d\). Here, the proof, that the iterated Tverberg algorithm calculates an \(\Omega(\frac{1}{d^2})\)-center in time sub-exponential in \(d\), is given and the usage of higher order Tverberg partitions to speed up the running time of the deterministic algorithm and to improve the approximation ration of the randomized version is shown, too. A center point as a natural generalization of the median to higher dimensions is used as robust estimators in statistics, because they are invariant under affine transformations and robust to outliers. Furthermore, the computation of centre point can be used in computational geometry when solving the mesh partitioning problem.