Stable Roommates for Weighted Straight Skeletons
Thérèse Biedl, Stefan G. Huber, Peter Palfrader · 2014
In this paper, we fill in a gap in the wavefront-based definition of weighted straight skeletons in the pres-ence of multiple simultaneous, co-located split events. We interpret the need to pair up wavefront edges to restore planarity as a particular matching problem. Our results on a stable roommate problem defined on a directed pseudo-line arrangement show that our method always yields a solution. We thereby com-plete the definition of weighted straight skeletons. 1