Detecting weakly simple polygons

With Hsien-Chih Chang* and Chao Xu*.

Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms, 1655–1670, 2015.

• Download SODA version:

Abstract:

A closed curve in the plane is weakly simple if it is the limit (in the Fréchet metric) of a sequence of simple closed curves. We describe an algorithm to determine whether a closed walk of length n in a simple plane graph is weakly simple in O(n log n) time, improving an earlier O(n³)-time algorithm of Cortese et al.. As an immediate corollary, we obtain the first efficient algorithm to determine whether an arbitrary n-vertex polygon is weakly simple; our algorithm runs in O(n² log n) time. We also describe algorithms that detect weak simplicity in O(n log n) time for two interesting classes of polygons. Finally, we discuss subtle errors in several previously published definitions of weak simplicity.

Dedicated with thanks to our colleague Ferran Hurtado (1951–2014)

Publications - Jeff Erickson (jeffe@cs.uiuc.edu) 25 Mar 2016