Optimally computing a shortest weakly visible line segment inside a simple polygon (Q1614066): Difference between revisions

The authors present a linear-time algorithm (which is optimal) for the following problem: Given a simple polygon, either compute a shortest line segment such that every point on the boundary of the polygon is visible from some point on the line segment (weakly internal visible), or report that such a segment does not exist. This algorithm is a significant improvement over another linear-time algorithm presented by some of the authors [\textit{G. Das} and \textit{G. Narasinhan}, Proc. 10th Annual ACM Symp. on Computational Geometry, 259-268 (1994)] since the new algorithm does not use some tools used in the previous one (as Chazelle's linear-time triangulation algorithm) that made the first algorithm impractical.