We present an O(nlog n) -time algorithm that determines whether a given n-gon in the plane is weakly simple. This improves upon an O(n2log n) -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.
- Combinatorial embedding
- Simple polygon
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics