SKRW 2014 – Topics
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 , 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 . For non-degenerate polygons it is expected time. If input is -bit rational then , including non-degenerate polygons. Very recent arxiv paper: time for simple polygons and for a PSLG with components, if the mc graph is given. An efficient reduction of SK to MCG would be already interessting.
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 time, which gives a randomized straight skeleton algorithm, where 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.