Straight skeleton of a simple polygon

Definitions and mathematical statement

Let $P\subset{\mathbb{R}}^2$ be a simple polygon with $n$ vertices. Its unweighted straight skeleton is the embedded graph traced by wavefront vertices when each polygon edge moves inward parallel to itself at unit normal speed and the wavefront is updated at edge-collapse and split events. The usual definition includes the traces up to disappearance of the wavefront; handling simultaneous events and other degeneracies requires a specified convention.

The source asks whether the straight skeleton can be constructed in near-linear time, and asks for its optimal computational complexity, including the subclass whose reflex angles are bounded away from zero. Under a common meaning of near-linear, the first target would be an algorithm with running time \[ O\left(n(\log n)^c\right) \] for some fixed constant $c$, uniformly over the permitted inputs. The source does not itself fix that meaning, the computation model, coordinate representation, permitted randomization, or degeneracy assumptions.

For a reflex vertex the interior angle $\alpha$ lies in $(\pi,2\pi)$, so an assertion that the interior angle itself is bounded away from zero is automatic. The intended "reflex angle" may instead be an excess, a complementary angle, or a wavefront-relevant angle. A precise restricted-input question needs that quantity and a positive lower bound, with its dependence in the running time, stated explicitly.

The supplied summary reports an affirmative near-linear result with qualifications: Vigneron--Yan (2014) computes the straight skeleton in expected time $O(n\log^3 n)$ for simple polygons with rational coordinates of $O(\log n)$ bits. It also reports an earlier $O(n^{4/3+\varepsilon})$ bound for general non-degenerate inputs. The rational bit-length and expected-time qualifications are part of the reported result; neither is silently removed. The summary does not give a matching lower bound, resolve every input model, or state a separate result for the angle-restricted class.

Short English statement

Determine the optimal time to construct the straight skeleton of a simple polygon, with particular attention to near-linear algorithms and a specified lower-angle restriction at reflex vertices. The registry marks the record solved in the literature based on the reported expected $O(n\log^3n)$ algorithm for small-bit rational coordinates. That supplies the stated near-linear special setting; the record does not justify treating every optimal-complexity or angle-restricted variant as resolved.

The source index warns that it has not been systematically updated since 2001. Its access date 2026-07-29 and the supplied later research summary are retained as provenance, without a new literature-status assertion.

Sources

• Local UnsolvedMath registry, permanent ID 3800016, source code catalogue entry, "Straight skeleton of a simple polygon," attributed to Jeff Erickson and cited proposers. Dataset curation and metadata: Ulam AI and UnsolvedMath Contributors, CC BY 4.0.
• Erickson, Open Problems in Computational Geometry, item "Straight skeleton of a simple polygon," https://jeffe.cs.illinois.edu/open/; HTML extraction, accessed 2026-07-29. The source warns of no systematic updating since 2001.
• Vigneron--Yan (2014), as cited in the supplied research summary for the expected $O(n\log^3n)$ bound. No title, publication details, or item-specific locator is supplied. The earlier $O(n^{4/3+\varepsilon})$ result is not separately identified.
• Source provenance marks status evidence NEEDS_REVIEW and rights NEEDS_REVIEW: public access was verified, but redistribution permission was not established. This qualification is separate from the dataset licence.