@inproceedings{2ba28e78a45e4b77b05e1287dec943db,
title = "Minimum-link paths among obstacles in the plane",
abstract = "Given a set of nonintersecting polygonal obstacles in the plane, the link distance between two points s and t is the minimum number of edges required to form a polygonal path connecting s to t that avoids all obstacles. We present an algorithm that computes the link distance (and a corresponding minimum-link path) between two points in time O(Eα(n) log2 n) (and space O(E)), where n is the total number of edges of the obstacles, E is the size of the visibility graph, and α(n) denotes the extremely slowly growing inverse of Ackermann's function.",
author = "Mitchell, \{Joseph S.B.\} and Gunter Rote and Gerhard Woeginger",
year = "1990",
doi = "10.1145/98524.98537",
language = "English",
isbn = "0897913620",
series = "Proc Sixth Annu Symp Comput Geom",
publisher = "Publ by ACM",
pages = "63--72",
booktitle = "Proc Sixth Annu Symp Comput Geom",
note = "Proceedings of the Sixth Annual Symposium on Computational Geometry ; Conference date: 06-06-1990 Through 08-06-1990",
}