A simple algorithm for computing positively weighted straight skeletons of monotone polygons

2014/09/30 by Thérèse Biedl, Martin Held, Stefan Huber +2 · 1 citation
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Mathematics and Applications #Data Management and Algorithms #Monotone polygon #Polygon (computer graphics) #Combinatorics #Simple (philosophy) #Rectilinear polygon #Simple polygon #Algorithm #Mathematics #SIMPLE algorithm #Polygon covering #Computational geometry #Computer science #Geometry

paper · pdf · doi:10.1016/j.ipl.2014.09.021

openalex publication_date 2014/09/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/02

Abstract

We study the characteristics of straight skeletons of monotone polygonal chains and use them to devise an algorithm for computing positively weighted straight skeletons of monotone polygons. Our algorithm runs in O(nlog⁡n) time and O(n) space, where n denotes the number of vertices of the polygon.

Citations

• Raising Roofs, Crashing Cycles, and Playing Pool: Applications of a Data Structure for Finding Pairwise Interactions

Cited by

• Straight skeleton [wikipedia]