Optimal linear-time algorithm for the shortest illuminating line segment in a polygon
Gautam Das, Giri Narasimhan · 1994
Given a simple polygon, we present an optimal linear-time algorithm that computes the shortest illuminating line segment, if one exists; else it reports that none exists. This solves an intriguing open problem by improving the O(n log n)-time algorithm [Ke87] for computing such a segment. 1