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.
« November 2017 »
November
SuMoTuWeThFrSa
1234
567891011
12131415161718
19202122232425
2627282930