Reprint of: Weighted straight skeletons in the plane

Biedl, Therese; Held, Martin; Huber, Stefan; Kaaser, Dominik; Palfrader, Peter

Reprint of: Weighted straight skeletons in the plane

Biedl T, Held M, Huber S, Kaaser D, Palfrader P. 2015. Reprint of: Weighted straight skeletons in the plane. Computational Geometry: Theory and Applications. 48(5), 429–442.

Download

IST-2016-475-v1+1_1-s2.0-S092577211500005X-main.pdf 508.38 KB

DOI

10.1016/j.comgeo.2015.01.004

Journal Article | Published | English

Scopus indexed

Author

Biedl, Therese; Held, Martin; Huber, Stefan^ISTA ; Kaaser, Dominik; Palfrader, Peter

Department

Edelsbrunner Group

Abstract

We investigate weighted straight skeletons from a geometric, graph-theoretical, and combinatorial point of view. We start with a thorough definition and shed light on some ambiguity issues in the procedural definition. We investigate the geometry, combinatorics, and topology of faces and the roof model, and we discuss in which cases a weighted straight skeleton is connected. Finally, we show that the weighted straight skeleton of even a simple polygon may be non-planar and may contain cycles, and we discuss under which restrictions on the weights and/or the input polygon the weighted straight skeleton still behaves similar to its unweighted counterpart. In particular, we obtain a non-procedural description and a linear-time construction algorithm for the straight skeleton of strictly convex polygons with arbitrary weights.

Publishing Year

2015

Date Published

2015-07-01

Journal Title

Computational Geometry: Theory and Applications

Volume

Issue

Page

429 - 442

IST-REx-ID

1584

Cite this

Biedl T, Held M, Huber S, Kaaser D, Palfrader P. Reprint of: Weighted straight skeletons in the plane. Computational Geometry: Theory and Applications. 2015;48(5):429-442. doi:10.1016/j.comgeo.2015.01.004

Biedl, T., Held, M., Huber, S., Kaaser, D., & Palfrader, P. (2015). Reprint of: Weighted straight skeletons in the plane. Computational Geometry: Theory and Applications. Elsevier. https://doi.org/10.1016/j.comgeo.2015.01.004

Biedl, Therese, Martin Held, Stefan Huber, Dominik Kaaser, and Peter Palfrader. “Reprint of: Weighted Straight Skeletons in the Plane.” Computational Geometry: Theory and Applications. Elsevier, 2015. https://doi.org/10.1016/j.comgeo.2015.01.004.

T. Biedl, M. Held, S. Huber, D. Kaaser, and P. Palfrader, “Reprint of: Weighted straight skeletons in the plane,” Computational Geometry: Theory and Applications, vol. 48, no. 5. Elsevier, pp. 429–442, 2015.

Biedl T, Held M, Huber S, Kaaser D, Palfrader P. 2015. Reprint of: Weighted straight skeletons in the plane. Computational Geometry: Theory and Applications. 48(5), 429–442.

Biedl, Therese, et al. “Reprint of: Weighted Straight Skeletons in the Plane.” Computational Geometry: Theory and Applications, vol. 48, no. 5, Elsevier, 2015, pp. 429–42, doi:10.1016/j.comgeo.2015.01.004.

All files available under the following license(s):

Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):