Recognizing Weakly Simple Polygons

We present an $$O(n\log n)$$O(nlogn)-time algorithm that determines whether a given n-gon in the plane is weakly simple. This improves upon an $$O(n^2\log n)$$O(n2logn)-time algorithm by Chang et al. (Proceedings of the 26th ACM-SIAM symposium on discrete algorithm, SIAM, 2015). Weakly simple polygons are required as input for several geometric algorithms. As such, recognizing simple or weakly simple polygons is a fundamental problem.