Personal tools
 

Finding Weakly Simple Polygons

— filed under:

Jeff Erickson, University of Illinois at Urbana-Champaign

What
  • Computer Science Seminar
When Fri, Oct 28, 2016
from 03:10 PM to 04:00 PM
Where Ritter Hall 115
Add event to calendar vCal
iCal
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. This is joint work with Hugo Akitaya, Greg Aloupis, Hsien-Chih Chang, Csaba Tóth, and Chao Xu.
« September 2017 »
September
SuMoTuWeThFrSa
12
3456789
10111213141516
17181920212223
24252627282930