On merging straight skeletons

F. Aurenhammer, M. Steinkogler

Research output: Chapter in Book/Report/Conference proceedingConference paperpeer-review


The search for efficient algorithms to compute the straight skeletons of a simple polygon has resulted in a variety of algorithms. We present a new approach that applies the divide-and-conquer paradigm with the divide step based on the motorcycle graph. A practical randomized algorithm is obtained that derives the straight skeleton from the motorcycle graph, with an expected running time of O(d n log n), where d is the decomposition depth of the motorcycle graph.
Original languageEnglish
Title of host publicationProc. 34th European Workshop on Computational Geometry (EuroCG'18)
Place of PublicationBerlin, Germany
Publication statusPublished - 2018


Dive into the research topics of 'On merging straight skeletons'. Together they form a unique fingerprint.

Cite this