Cargando…

Weighted straight skeletons in the plane()

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

Descripción completa

Detalles Bibliográficos
Autores principales: Biedl, Therese, Held, Martin, Huber, Stefan, Kaaser, Dominik, Palfrader, Peter
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Elsevier 2015
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4235777/
https://www.ncbi.nlm.nih.gov/pubmed/25648398
http://dx.doi.org/10.1016/j.comgeo.2014.08.006
Descripción
Sumario: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.