Recognizing weakly simple polygons

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

To appear in Discrete & Computational Geometry, 2017
(special issue of invited papers from the 32nd International Symposium on Computational Geometry)

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

arXiv:1603.07401


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) 16 Aug 2017