Algorithms for Radon partitions with tolerance

DOI10.1016/J.DAM.2021.09.014MaRDI QIDQ5918766zbMATH OpenOpenAlexFDO

Authors 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

linear classifiersRadon partitionstoleranceTverberg partitionsTverberg's theorem

Mathematics Subject Classification ID

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

Recommendations

• Algorithms for Radon partitions with tolerance
• ALGORITHMS FOR TOLERANT TVERBERG PARTITIONS
• Algorithms for tolerated Tverberg partitions
• New lower bounds for Tverberg partitions with tolerance in the plane
• Tolerance for colorful Tverberg partitions

Cites work

• 10 points in dimension 4 not projectively equivalent to the vertices of a convex polytope
• A generalisation of Tverberg's theorem
• A Generalization of Radon's Theorem
• A note on the Tolerant Tverberg Theorem
• A Theorem on General Measure
• Algorithms for center and Tverberg points
• ALGORITHMS FOR TOLERANT TVERBERG PARTITIONS
• Algorithms for weak and wide separation of sets
• AN OPTIMAL ALGORITHM FOR COMPUTING (≤K)-LEVELS, WITH APPLICATIONS
• Approximate centerpoints with proofs
• Approximating Tverberg points in linear time for any fixed dimension
• Beyond the Borsuk–Ulam Theorem: The Topological Tverberg Story
• Enumeration of Seven-Argument Threshold Functions
• scientific article; zbMATH DE number 1190538 (Why is no real title available?)
• scientific article; zbMATH DE number 3781091 (Why is no real title available?)
• scientific article; zbMATH DE number 480237 (Why is no real title available?)
• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• scientific article; zbMATH DE number 3199765 (Why is no real title available?)
• Improved Approximation Algorithms for Tverberg Partitions
• Lawrence oriented matroids and a problem of McMullen on projective equivalences of polytopes
• Low-Dimensional Linear Programming with Violations
• Minimizing the error of linear separators on linearly inseparable data
• New lower bounds for Tverberg partitions with tolerance in the plane
• On k-Hulls and Related Problems
• On a class of \(O(n^ 2)\) problems in computational geometry
• On geometric optimization with few violated constraints
• On Sets Projectively Equivalent to the Vertices of a Convex Polytope
• On the combinatorics of the 2-class classification problem
• On the number of separable partitions
• Projective equivalences of \(k\)-neighbourly polytopes
• Robust Tverberg and Colourful Carathéodory Results via Random Choice
• 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
• The number of partitions of a set of N points in k dimensions induced by hyperplanes
• Tverberg's Theorem at 50: Extensions and Counterexamples
• Tverberg’s theorem is 50 years old: A survey

Cited in

(6)

• The Radon-split and the Helly-core of a point configuration
• An application of the universality theorem for Tverberg partitions to data depth and hitting convex sets
• Algorithms for tolerated Tverberg partitions
• Algorithms for Radon partitions with tolerance
• Tolerant Radon partitions on the all-paths convexity in graphs
• Tolerant Radon partitions of induced path convexity in graphs

Describes a project that uses

Uses Software

• ElemStatLearn

This page was built for publication: Algorithms for Radon partitions with tolerance

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5918766)