Approximate centerpoints with proofs
type: Item
instance of: scholarly article
title: Approximate centerpoints with proofs
zbMATH Open document ID: 1206.65101
author: Donald R. Sheehy
author: Gary L. Miller
published in: Computational Geometry
publication date: 2010-09-02T00:00:00Z
review text: 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.
reviewed by: Ivana Linkeová
Mathematics Subject Classification ID: 65D18
Mathematics Subject Classification ID: 65D17
Mathematics Subject Classification ID: 65M50
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 65C60
zbMATH DE Number: 5777760
zbMATH Keywords: centre-point
zbMATH Keywords: deterministic algorithm
zbMATH Keywords: Tverberg theorem
zbMATH Keywords: Radon theorem
zbMATH Keywords: median
describes a project that uses: MESHPART
MaRDI profile type: Publication
full work available at URL: j.comgeo.2010.04.006
OpenAlex ID: W2215397208
cites work: Q5501289
cites work: APPROXIMATING CENTER POINTS WITH ITERATIVE RADON POINTS
cites work: On k-Hulls and Related Problems
cites work: Q5341481
cites work: Q4464662
cites work: Geometric medians
cites work: Geometric Mesh Partitioning: Implementation and Experiments
cites work: Computing a centerpoint of a finite planar set of points in linear time
cites work: Q2739351
cites work: Q4530626
cites work: A Theorem on General Measure
cites work: A Generalization of Radon's Theorem
cites work: Approximate center points in dense point sets
DOI: 10.1016/J.COMGEO.2010.04.006
description: scientific article; zbMATH DE number 5777760