Computing positively weighted straight skeletons of simple polygons based on a bisector arrangement
Günther Eder, Martin Held · Information Processing Letters · 2017
We extend the work by Huber and Held (IJCGA 2012) on straight-skeleton computation based on motorcycle graphs to positively weighted skeletons. Resorting to a line arrangement induced by the r reflex vertices of a simple n-vertex polygon P allows to compute the weighted straight skeleton of P in O(n2+r3k+nrlogn) time and O(n+kr) space, for an arbitrary positive integer k≤r.