Event Type:

Number Theory Seminar

Date/Time:

Friday, January 10, 2014 - 04:00

Location:

Wngr 285

Guest Speaker:

Institution:

Department of Computer Science, University of Illinois UC

Abstract:

A polygon is a closed piecewise-linear curve in the plane. A polygon is simple if its vertices are distinct and its edges are pairwise non-crossing, and weakly simple if it can be made simple by an arbitrarily small perturbation. We describe an algorithm to determine whether an arbitrary given polygon with n vertices is weakly simple in O(n\log n) time. Only exponential-time algorithms were previously known for this problem; in particular, characterizations of weakly simple polygons in terms of non-crossing subpaths and winding numbers, which have appeared many times in the literature since the 1980s, are incorrect. The main difficulty is dealing with "spurs", where two consecutive edges of the polygon overlap. As a key component of our result, we modify an algorithm of Cortese et al. [Graph Drawing 2005, Discrete Math. 2009] to determine whether a closed walk in an embedded graph can be perturbed to a simple closed curve, improving its running time from O(n^3) to O(n\log n).

This is work in progress with Hsien-Chih Chang and Chao Xu.