Lower bounds for the number of hyperplanes separating two finite sets of points

DOI10.1134/S0081543815050119MaRDI QIDQ492284zbMATH OpenFDO

Authors K. S. Kobylkin

Publication date 20 August 2015

Published in Proceedings of the Steklov Institute of Mathematics (Search for Journal in Brave)

zbMATH Keywords

Boolean function\(k\)-polyhedral separabilitycombinatorial discrepancymonochromatic island

Mathematics Subject Classification ID

Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35) Combinatorial complexity of geometric structures (52C45)

Recommendations

• On the complexity of polyhedral separability
• Polyhedral separability through successive LP
• Separation via polyhedral conic functions
• Bilinear separation of two sets in n-space
• The complexity of computing minimum separating polygons

Cites work

• scientific article; zbMATH DE number 3121295 (Why is no real title available?)
• scientific article; zbMATH DE number 5598224 (Why is no real title available?)
• scientific article; zbMATH DE number 3828715 (Why is no real title available?)
• scientific article; zbMATH DE number 4032498 (Why is no real title available?)
• scientific article; zbMATH DE number 1003231 (Why is no real title available?)
• scientific article; zbMATH DE number 1789912 (Why is no real title available?)
• scientific article; zbMATH DE number 1830740 (Why is no real title available?)
• A note on Sylvester’s four-point problem
• Algorithms for weak and wide separation of sets
• Committee constructions.
• Geometric discrepancy. An illustrated guide
• On Approximating the Depth and Related Problems
• On the complexity of polyhedral separability
• Power Diagrams: Properties, Algorithms and Applications
• Probability Inequalities for Sums of Bounded Random Variables
• Separation and approximation of polyhedral objects
• Sequential and parallel algorithms for finding a maximum convex polygon
• Sylvester's question: The probability that \(n\) points are in convex position
• The probabilistic method

Cited in

(7)

• The number of small semispaces of a finite set of points in the plane
• On sets defining few ordinary hyperplanes
• Separation of integer points by a hyperplane under some weak notions of discrete convexity
• SOME LOWER BOUNDS ON GEOMETRIC SEPARABILITY PROBLEMS
• Directed projection graph of \(N\)-dimensional hypercube and subhypercube decomposition of balanced linearly separable Boolean functions
• On the complexity of polyhedral separability
• Polyhedral separability through successive LP

This page was built for publication: Lower bounds for the number of hyperplanes separating two finite sets of points

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