SKRW 2014 – Topics

Martin Held

Non-trivial lower bounds on the complexity of SK of a polygon.

SH: Polygons w/ holes: reduction to sorting holes along x-axis; Reduction on radially sorting motorcycles; No non-trivial 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 non-degenerate 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 non-degenerate 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.

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 non-degenerate.
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.
Imprecise-input-type 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?

Pseudo-triangulations 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. Pseudo-triangulations, which are related to efficient ray shooting, might be useful for both, motorcycle graphs and straight skeletons.