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

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 for a disc between these points is known to require time nlog(n) at least, measured in suitable units. 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 the same computation time. This bound is matched by published algorithms.