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

• 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

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)

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)