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)

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 minimum spanning trees

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