SEPARATING POINTS BY AXIS-PARALLEL LINES

DOI10.1142/S0218195905001865MaRDI QIDQ3373055zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

complexityinteger programmingintegrality gappoint separationpolynomial-time algorithmLP-rounding\(d\)-approximation algorithm

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Recommendations

• Separating multi-color points on a plane with fewest axis-parallel lines
• scientific article; zbMATH DE number 6850368
• On the parameterized complexity of red-blue points separation
• On separating points by lines
• On the parameterized complexity of red-blue points separation

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Approximation algorithms for hitting objects with straight lines
• Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem
• ON PIERCING SETS OF AXIS-PARALLEL RECTANGLES AND RINGS
• Separability by two lines and by nearly straight polygonal chains
• Separating objects in the plane by wedges and strips

Cited in

(24)

• Parameterized Complexity of Stabbing Rectangles and Squares in the Plane
• On the parameterized complexity of red-blue points separation
• The \textsc{Red-Blue Separation} problem on graphs
• On the shortest separating cycle
• Approximation algorithms for aligning points
• scientific article; zbMATH DE number 6850368 (Why is no real title available?)
• Partial multicovering and the \(d\)-consecutive ones property
• On separating points by lines
• scientific article; zbMATH DE number 2079753 (Why is no real title available?)
• Fixed-parameter tractability and lower bounds for stabbing problems
• Approximation algorithms for orthogonal line centers
• Approximation algorithms for orthogonal line centers
• The shortest separating cycle problem
• Identification of points using disks
• Complexity and approximation for discriminating and identifying code problems in geometric setups
• The ``point goalie problem
• Separating overlapped intervals on a line
• Discriminating Codes in Geometric Setups
• Separating multi-color points on a plane with fewest axis-parallel lines
• On the parameterized complexity of red-blue points separation
• On the complexity of polyhedral separability
• The parameterized complexity of stabbing rectangles
• Approximation algorithms for aligning points
• The \textsc{red-blue separation} problem on graphs

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)