Algorithms for Radon partitions with tolerance

DOI10.1016/j.dam.2021.09.014zbMath1494.52005OpenAlexW4213390927MaRDI QIDQ5918766

Sergey Bereg, Mohammadreza Haghpanah

Publication date: 4 August 2022

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2021.09.014

zbMATH Keywords

toleranceTverberg's theoremTverberg partitionslinear classifiersRadon partitions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational aspects related to convexity (52B55) Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Helly-type theorems and geometric transversal theory (52A35)

Uses Software

• ElemStatLearn

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A generalisation of Tverberg's theorem
• Minimizing the error of linear separators on linearly inseparable data
• On the number of separable partitions
• Projective equivalences of \(k\)-neighbourly polytopes
• Equal coefficients and tolerance in coloured Tverberg partitions
• Algorithms for weak and wide separation of sets
• Approximate centerpoints with proofs
• On a class of \(O(n^ 2)\) problems in computational geometry
• On geometric optimization with few violated constraints
• New lower bounds for Tverberg partitions with tolerance in the plane
• A note on the Tolerant Tverberg Theorem
• On the combinatorics of the 2-class classification problem
• Tverberg's Theorem at 50: Extensions and Counterexamples
• On k-Hulls and Related Problems
• Beyond the Borsuk–Ulam Theorem: The Topological Tverberg Story
• Robust Tverberg and Colourful Carathéodory Results via Random Choice
• Tverberg’s theorem is 50 years old: A survey
• Algorithms for center and Tverberg points
• Stochastic Tverberg Theorems With Applications in Multiclass Logistic Regression, Separability, and Centerpoints of Data
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• ALGORITHMS FOR TOLERANT TVERBERG PARTITIONS
• Low-Dimensional Linear Programming with Violations
• A Generalization of Radon's Theorem
• Enumeration of Seven-Argument Threshold Functions
• The number of partitions of a set of N points in k dimensions induced by hyperplanes
• On Sets Projectively Equivalent to the Vertices of a Convex Polytope
• AN OPTIMAL ALGORITHM FOR COMPUTING (≤K)-LEVELS, WITH APPLICATIONS
• A Theorem on General Measure
• Approximating Tverberg points in linear time for any fixed dimension
• 10 points in dimension 4 not projectively equivalent to the vertices of a convex polytope
• Lawrence oriented matroids and a problem of McMullen on projective equivalences of polytopes
• Improved Approximation Algorithms for Tverberg Partitions