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.

arXiv:1603.07401

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


Abstract:
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 (jeffe@cs.uiuc.edu) 02 Sep 2016