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
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
