Recognizing weakly simple polygons

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

Discrete & Computational Geometry 58(4):785–821, 2017.
(Special issue of invited papers from the 32nd International Symposium on Computational Geometry)

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) 05 Apr 2018