MINIMUM-LINK C-ORIENTED PATHS: SINGLE-SOURCE QUERIES
JOHN ADEGEEST, Mark Overmars, Jack Scott Snoeyink · International Journal of Computational Geometry & Applications · 1994
We consider paths composed of a minimum number of line segments parallel to a fixed set of c orientations that avoid a set of obstacles in the plane. We preprocess n line segment obstacles with disjoint interiors and a starting point A into a data structure using O(cn) space. With this data structure, we can determine the minimum number of line segments l of a path from A to a query point B in O(c log n) time and construct a path in additional O(l) time. Preprocessing takes O(c2n log n) time and space or O(c2n log 2 n) time and O(c2n) space. Usually c is a constant — as an example, c = 2 for rectilinear paths.