SEPARATING POINTS BY AXIS-PARALLEL LINES
From MaRDI portal
Publication:3373055
DOI10.1142/S0218195905001865zbMath1101.65020OpenAlexW2112104566MaRDI QIDQ3373055
Adrian Dumitrescu, Gruia Călinescu, Peng-Jun Wan, Howard J. Karloff
Publication date: 13 March 2006
Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s0218195905001865
complexityinteger programmingpolynomial-time algorithmpoint separationintegrality gapLP-rounding\(d\)-approximation algorithm
Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Complexity and performance of numerical algorithms (65Y20)
Related Items (14)
Identification of points using disks ⋮ Approximation algorithms for orthogonal line centers ⋮ Fixed-parameter tractability and lower bounds for stabbing problems ⋮ The \textsc{red-blue separation} problem on graphs ⋮ Partial multicovering and the \(d\)-consecutive ones property ⋮ Complexity and approximation for discriminating and identifying code problems in geometric setups ⋮ The \textsc{Red-Blue Separation} problem on graphs ⋮ The parameterized complexity of stabbing rectangles ⋮ Approximation algorithms for orthogonal line centers ⋮ On separating points by lines ⋮ Discriminating Codes in Geometric Setups ⋮ Parameterized Complexity of Stabbing Rectangles and Squares in the Plane ⋮ On the shortest separating cycle ⋮ On the Parameterized Complexity of Red-Blue Points Separation
Cites Work
- Unnamed Item
- Approximation algorithms for hitting objects with straight lines
- Separability by two lines and by nearly straight polygonal chains
- Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem
- ON PIERCING SETS OF AXIS-PARALLEL RECTANGLES AND RINGS
- Separating objects in the plane by wedges and strips
This page was built for publication: SEPARATING POINTS BY AXIS-PARALLEL LINES