ON CONNECTING RED AND BLUE RECTILINEAR POLYGONAL OBSTACLES WITH NONINTERSECTING MONOTONE RECTILINEAR PATHS

DOI10.1142/S0218195901000547zbMath1074.68628MaRDI QIDQ4682161

Danny Z. Chen, Mikhail J. Atallah

Publication date: 10 June 2005

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0218195901000547

zbMATH Keywords

numbering scheme; Rectilinear paths; red/blue matching; staircase separators

Mathematics Subject Classification ID

52B55: Computational aspects related to convexity

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

Related Items

Planar Bichromatic Bottleneck Spanning Trees, Planar bichromatic minimum spanning trees, Bottleneck bichromatic full Steiner trees, Plane bichromatic trees of low degree

Cites Work

• On the X-Y convex hull of a set of X-Y polygons
• A matching problem in the plane
• Finding the convex hull of a sorted point set in parallel
• A nonuniform matroid which violates the isotopy conjecture
• Maintenance of configurations in the plane
• Topological numbering of features on a mesh
• On parallel rectilinear obstacle-avoiding paths
• Rectilinear short path queries among rectangular obstacles
• Parallel algorithms for maximum matching in complements of interval graphs and related problems
• On Some Distance Problems in Fixed Orientations
• An Efficient Parallel Biconnectivity Algorithm
• Time Redundant Fault-Location in Bit-Sliced ALU's
• Cascading Divide-and-Conquer: A Technique for Designing Parallel Algorithms
• Finding minimum rectilinear distance paths in the presence of barriers
• Lower Bounds for Algebraic Computation Trees of Functions with Finite Domains
• Rectilinear Path Problems among Rectilinear Obstacles Revisited
• Shortest Path Queries Among Weighted Obstacles in the Rectilinear Plane