A tight lower bound for the complexity of path-planning for a disc (Q1111039)

Given two points in a planar room with polygonal boundary and polygonal obstacles (having a total of n corners), the problem of finding a shortest obstacle-avoiding path between them is known to require \(\Omega\) (n log n) time. In this article it is shown that the problem of finding any obstacle-avoiding path for a disc in the room, or even deciding whether such a path exists, requires \(\Omega\) (n log n) time. This bound is met by the published algorithms.