paper

Recognizing Weakly Simple Polygons

arXiv:1603.07401

Abstract

We present an $O (n lo g n)$ -time algorithm that determines whether a given planar $n$ -gon is weakly simple. This improves upon an $O (n^{2} lo g n)$ -time algorithm by Chang, Erickson, and Xu (2015). 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.

35 pages, 28 figures. A 15-page extended abstract has appeared in the Proceeding of the 32nd International Symposium on Computational Geometry (Boston, MA, 2016)