On graphs preserving rectilinear shortest paths in the presence of obstacles (Q1179762)

For solving global wiring problems in physical VLSI circuit design, two stages are usually considered. The first stage is to compute from the layout geometry a graph that preserves all shortest paths between pairs of relevant points. The second stage is to operate on that graph for computing shortest paths, Steiner minimal tree approximations or the like. For a set of points and a set of simple orthogonal polygons as obstacles in the plane, with \(n\) input points (polygon corners or others) the author shows how a shortest paths preserving graph of size \(O(n \log n)\) can be computed in time \(O(n \log n)\) in the worst case, with space \(O(n)\).