# 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.

## 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 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?

## Thomas Hackl

• 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.