SEPARATING POINTS BY AXIS-PARALLEL LINES
DOI10.1142/S0218195905001865zbMATH Open1101.65020OpenAlexW2112104566MaRDI QIDQ3373055FDOQ3373055
Authors: Gruia Calinescu, Adrian Dumitrescu, Peng-Jun Wan, Howard 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
Recommendations
complexityinteger programmingintegrality gappoint separationpolynomial-time algorithmLP-rounding\(d\)-approximation algorithm
Complexity and performance of numerical algorithms (65Y20) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)
Cites Work
- Title not available (Why is that?)
- Approximation algorithms for hitting objects with straight lines
- Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem
- Separating objects in the plane by wedges and strips
- Separability by two lines and by nearly straight polygonal chains
- ON PIERCING SETS OF AXIS-PARALLEL RECTANGLES AND RINGS
Cited In (24)
- On separating points by lines
- Discriminating Codes in Geometric Setups
- The shortest separating cycle problem
- The parameterized complexity of stabbing rectangles
- Partial multicovering and the \(d\)-consecutive ones property
- The ``point goalie problem
- On the shortest separating cycle
- Separating overlapped intervals on a line
- Separating multi-color points on a plane with fewest axis-parallel lines
- Approximation algorithms for aligning points
- Identification of points using disks
- On the complexity of polyhedral separability
- The \textsc{Red-Blue Separation} problem on graphs
- Title not available (Why is that?)
- Parameterized Complexity of Stabbing Rectangles and Squares in the Plane
- On the parameterized complexity of red-blue points separation
- On the parameterized complexity of red-blue points separation
- The \textsc{red-blue separation} problem on graphs
- Approximation algorithms for aligning points
- Title not available (Why is that?)
- Fixed-parameter tractability and lower bounds for stabbing problems
- Complexity and approximation for discriminating and identifying code problems in geometric setups
- Approximation algorithms for orthogonal line centers
- Approximation algorithms for orthogonal line centers
This page was built for publication: SEPARATING POINTS BY AXIS-PARALLEL LINES
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3373055)