Recognizing Weakly Simple Polygons

Hugo Akitaya, Greg Aloupis, Jeff Erickson +1

We present an $O(n\log n)$-time algorithm that determines whether a given planar $n$-gon is weakly simple. This improves upon an $O(n^2\log n)$-time algorithm by Chang, Erickson, a…