On separating points by lines
From MaRDI portal
Publication:1985301
DOI10.1007/s00454-019-00103-zzbMath1436.05019arXiv1706.02004OpenAlexW2947905785WikidataQ127801648 ScholiaQ127801648MaRDI QIDQ1985301
Mitchell Jones, Sariel Har-Peled
Publication date: 7 April 2020
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1706.02004
Partitions of sets (05A18) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (5)
The \textsc{red-blue separation} problem on graphs ⋮ Complexity and approximation for discriminating and identifying code problems in geometric setups ⋮ The \textsc{Red-Blue Separation} problem on graphs ⋮ Few cuts meet many point sets ⋮ Discriminating Codes in Geometric Setups
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Generalized ham-sandwich cuts
- A deterministic view of random sampling and its use in geometry
- \(\epsilon\)-nets and simplex range queries
- Efficient partition trees
- Shattering a set of objects in 2D
- Quasi-optimal range searching in spaces of finite VC-dimension
- Almost optimal set covers in finite VC-dimension
- On simple polygonalizations with optimal area
- Near-linear approximation algorithms for geometric hitting sets
- Peeling the Grid
- Longest convex chains
- Reducing the Dimensionality of Data with Neural Networks
- SEPARATING POINTS BY AXIS-PARALLEL LINES
- A linear algorithm for determining the separation of convex polyhedra
- Computing Many Faces in Arrangements of Lines and Segments
- Counting the onion
- Near-Linear Algorithms for Geometric Hitting Sets and Set Covers
- Algorithms for polytope covering and approximation
- On Range Searching with Semialgebraic Sets. II
- Concentration of Measure for the Analysis of Randomized Algorithms
This page was built for publication: On separating points by lines