The visibility graph contains a bounded-degree spanner.
Gautam Das · 1997
Given a collection of polygonal obstacles with n vertices on the place, and any t ? 1, we present an O(n log n) time algorithm that constructs a bounded-degree t-spanner of the visibility graph, without first having to construct the visibility graph.