Distance problems in computational geometry with fixed orientations

Abstract

In computational geometry, problems involving only rectilinear objects with edges parallel to the x -and y-axes have attracted great attention. They are often easier to solve than the same problems for arbitrary objects, and solutions are of high practical value, for instance in VLSI design. This is because in VLSI design technology requirements often dictate the use of only two orthogonal orientations for the boundary edges of objects as well as wires.