Recognizing Geometric Trees as Positively Weighted Straight Skeletons and Reconstructing Their Input
Günther Eder, Martin Held, Peter Palfrader · International Journal of Computational Geometry & Applications · 2019
We extend results by Biedl et al. (ISVD’13) on the recognition and reconstruction of straight skeletons: Given a geometric tree [Formula: see text], can we recognize whether [Formula: see text] resembles a weighted straight skeleton [Formula: see text] and, if so, can we reconstruct an appropriate polygonal input [Formula: see text] and an appropriate positive weight function [Formula: see text] such that [Formula: see text]? We show that a solution polygon [Formula: see text] and a weight function [Formula: see text] can be found in [Formula: see text] time and space for a geometric tree [Formula: see text] with [Formula: see text] faces if at most one node of [Formula: see text] has two incident edges that span an angle greater than [Formula: see text]. In addition, we show that [Formula: see text] implicitly encodes enough information such that all other weighted bisectors of any solution [Formula: see text] can be obtained from [Formula: see text] without explicitly computing [Formula: see text].