An efficient direct approach for computing shortest rectilinear paths among obstacles in a two-layer interconnection model

DOI10.1016/S0925-7721(01)00005-0zbMath0976.68164OpenAlexW1496291263MaRDI QIDQ5943315

Danny Z. Chen, Jinhui Xu

Publication date: 27 September 2001

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0925-7721(01)00005-0

zbMATH Keywords

integer data structurestwo-layer interconnection modelVLSI routing

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.) (68W35)

Related Items

Finding shortest path in the presence of barriers: an alternate approach

Cites Work

• Unnamed Item
• Unnamed Item
• \(L_ 1\) shortest paths among polygonal obstacles in the plane
• Preserving order in a forest in less than logarithmic time and linear space
• Rectilinear paths among rectilinear obstacles
• Optimal Point Location in a Monotone Subdivision
• Dynamic orthogonal segment intersection search
• Optimal Search in Planar Subdivisions
• SHORTEST RECTILINEAR PATHS AMONG WEIGHTED OBSTACLE
• ON BENDS AND LENGTHS OF RECTILINEAR PATHS: A GRAPH-THEORETIC APPROACH
• SHORTEST PATH QUERIES IN RECTILINEAR WORLDS
• Design and implementation of an efficient priority queue
• Finding Rectilinear Paths Among Obstacles in a Two-Layer Interconnection Model
• On bends and distances of paths among obstacles in two-layer interconnection model
• Rectilinear Path Problems among Rectilinear Obstacles Revisited
• Shortest Path Queries Among Weighted Obstacles in the Rectilinear Plane
• Fibonacci heaps and their uses in improved network optimization algorithms
• SHORTEST PATHS AMONG OBSTACLES IN THE PLANE