https://www.zhuzhugst.com/ 2026-04-22T05:35:06+00:00 https://www.zhuzhugst.com/ https://www.zhuzhugst.com/lib/exe/fetch.php?media=logo.png text/html 2025-09-25T06:54:26+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.zhuzhugst.com/doku.php?id=%E7%9B%B4%E9%AA%A8%E6%9E%B6%E7%9A%84%E7%A0%94%E7%A9%B6:introduction:prior_work:runtime_bounds_for_the_straight_skeleton&rev=1758783266&do=diff To the best of our knowledge, the currently best known lower bound to compute the straight skeleton of a simple polygon with $n$ vertices is Ω(n). In the convex case a simulation of the propagating wavefront gives us an almost optimal algorithm using O(n log n) time, see Section 1.4.2.1. For the more general case of monotone polygons, Das et al. [DMN+10] presented an O(n log n) algorithm.$a_k$