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

DOI10.1134/S0081543815050119zbMATH Open1327.52041MaRDI QIDQ492284FDOQ492284

Authors: K. S. Kobylkin 

Publication date: 20 August 2015

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

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

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)

Cites Work

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

Cited In (7)

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

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)