Algorithms Seminar

Finding Weakly Simple Polygons

Speaker:Jeff Erickson
Date: Thursday, December 1, 2016
Time: 12:00pm - 1:00pm
Location: D344 LSRC, Duke

Abstract

A polygon in the plane is weakly simple if an arbitrarily small perturbation of its vertices removes all self-intersections. Weakly simple polygons arise naturally as degenerate inputs or as intermediate constructions in several geometric algorithms; they also have strong connections to problems in graph drawing, mechanical linkage analysis, and topological embedding invariants. Deciding whether a given polygon is weakly simple is surprisingly subtle; several published definitions and algorithms are incorrect. I will describe several algorithms for this problem, the fastest of which runs in O(n log n) time, along with several interesting structural results. Portions of this talk are joint work with Hugo Akitaya, Greg Aloupis, Hsien-Chih Chang, Csaba Tóth, and Chao Xu, published at SODA 2015 and SOCG 2016.

Biography

Jeff Erickson is a Professor of Computer Science at the University of Illinois at Urbana-Champaign. He is a computational geometer/topologist with more general interests in algorithms, data structures, and lower bounds.