SEPARATING POINTS BY AXIS-PARALLEL LINES

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

zbMATH Keywords

complexityinteger programmingpolynomial-time algorithmpoint separationintegrality gapLP-rounding\(d\)-approximation algorithm

Mathematics Subject Classification ID

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