We present an $O(nlog n)$-time algorithm that determines whether a given planar $n$-gon is weakly simple. This improves upon an $O(n^2log n)$-time algorithm by Chang, Erickson, and Xu (2015). Weakly simple polygons are required as input for several geometric algorithms. As such, how to recognize simple or weakly simple polygons is a fundamental question.
تحميل البحث