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