Recognizing weakly simple polygons

With Hugo Akitaya*, Greg Aloupis, and Csaba Tóth

Proceedings of the 32nd International Symposium on Computational Geometry, 8:1--8:16, 2016.


Submitted by invitation to the special issue of Discrete & Computational Geometry devoted to the conference.

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² log n)-time algorithm by Chang, Erickson, and Xu. 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.

Publications - Jeff Erickson ( 02 Sep 2016