Approximating Tverberg points in linear time for any fixed dimension

DOI10.1007/s00454-013-9528-7zbMath1298.68281OpenAlexW2086902521MaRDI QIDQ5891192

Daniel Werner, Wolfgang Mulzer

Publication date: 23 September 2013

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-013-9528-7

zbMATH Keywords

approximationdiscrete geometryhigh dimensioncenterpointTverberg theorem

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35) Approximation algorithms (68W25)

Related Items (12)

Stochastic Tverberg Theorems With Applications in Multiclass Logistic Regression, Separability, and Centerpoints of Data ⋮ Graph-theoretic approaches for analyzing the resilience of distributed control systems: a tutorial and survey ⋮ Helly’s theorem: New variations and applications ⋮ Computational aspects of the colorful Carathéodory theorem ⋮ Algorithms for Radon partitions with tolerance ⋮ Unnamed Item ⋮ Tverberg’s theorem is 50 years old: A survey ⋮ Resilient distributed vector consensus using centerpoint ⋮ The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg ⋮ Tverberg theorems over discrete sets of points ⋮ ALGORITHMS FOR TOLERANT TVERBERG PARTITIONS ⋮ No-dimensional Tverberg theorems and algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximate centerpoints with proofs
• Geometric algorithms and combinatorial optimization.
• On the complexity of the parity argument and other inefficient proofs of existence
• Computing a centerpoint of a finite planar set of points in linear time
• A Further Generalization of the Colourful Carathéodory Theorem
• A Generalization of Radon's Theorem
• Algorithms for center and Tverberg points
• APPROXIMATING CENTER POINTS WITH ITERATIVE RADON POINTS
• A Theorem on General Measure

This page was built for publication: Approximating Tverberg points in linear time for any fixed dimension