SKRW 2014 – Topics
Martin Held

Nontrivial lower bounds on the complexity of SK of a polygon.
SH: Polygons w/ holes: reduction to sorting holes along xaxis; Reduction on radially sorting motorcycles; No nontrivial lower bound for simple polygons other than \(\Omega(n)\), maybe optimal?

Better upper bounds on the complexity of SK of a polygon, or special classes of polygons.
SH: For arbitrary polygons, the best upper bound is still \(O(n^{17/11+\epsilon})\). For nondegenerate polygons it is \(O(n \sqrt{h+1} \log^2 n + n^{4/3+\epsilon})\) expected time. If input is \(O(\log n)\)bit rational then \(O(n \sqrt{h+1} \log^3 n)\), including nondegenerate polygons. Very recent arxiv paper: \(O(n \log n)\) time for simple polygons and \(O(n \log n \log m)\) for a PSLG with \(m\) components, if the mc graph is given. An efficient reduction of SK to MCG would be already interessting.

3D.
SH: Need to read the recent results by Gernot and Franz.
Therese Biedl

Study Cheng & Vigneron’s ESA’2014 paper.
They reduce the computation of straight skeletons of polygons to motorcycle graphs in \(O(n \log n \log r)\) time, which gives a randomized \(O(n \sqrt{h+1} \log^2 n)\) straight skeleton algorithm, where \(h\) is the number of polygon holes, if the polygon is nondegenerate.

When is the straight skeleton of a polygon a caterpillar?
How quickly can we determine whether the straight skeleton of a polygon is a caterpillar?

Given a directed tree, can we find a polygon that has it as a straight skeleton?
We would like that the wavefront sweeps a directed tree edge according to its direction.

Impreciseinputtype straight skeleton computation.
The unstable nature of straight skeletons makes it harder to phrase a problem precisely. Maybe: Given a polygon, what is the smallest perturbation radius such that the combinatorial structure of the straight skeleton remains unchanged for all perturbations of polygon vertices?
Thomas Hackl

Pseudotriangulations for a faster straight skeleton algorithm.
SH: Though not following the punch line of pseudo triangulations, relevant related papers are Kaplan, Rubin, Sharir 2010 and Rubin 2013. Pseudotriangulations, which are related to efficient ray shooting, might be useful for both, motorcycle graphs and straight skeletons.