Time Complexity 355

Compute the Convex Hull of `n` arbitrary points in 2D (Worst-case optimal)

O(n log n)

- "Same as sorting." (Graham Scan, Divide-and-Conquer)

Compute the Convex Hull of a **Simple Polygon** with `n` vertices.

O(n)

- "Melkman's Algorithm" (Uses the "simple order" to avoid sorting).

Triangulate a **Simple Polygon** with `n` vertices (Theoretically best).

O(n)

- "Chazelle's Algorithm" (Treat as a black-box fact).

Triangulate *any* Planar Straight-Line Graph (PSLG) with `n` vertices (e.g., a polygon with holes).

O(n log n)

- "Plane Sweep" (Decomposes into monotone mountains).

Triangulate a **Monotone Mountain** with `n` vertices.

O(n)

- "Simple Ear Clipping" (No need to search for ears).

The `Triangulate` (Ear Clipping) algorithm from the textbook (Worst-case).

O(n²)

- "Repeatedly scanning for ears" (`n` ears to find, `O(n)` scan for each).

Gift-Wrapping (Jarvis March) algorithm for Convex Hull.

O(nh)

- "Output-Sensitive" (`h` steps, `O(n)` work per step).

QuickHull algorithm for Convex Hull (Worst-case).

O(nh) or O(n²)

- "Output-Sensitive, but can be bad" (like Quicksort).

Compute the number of reflex vertices in a simple `n`-gon.

O(n)

- "Single pass" (One `Left` test per vertex).

The Hertel-Mehlhorn algorithm for convex partitioning.

O(n)

- "Linear time 4-approximation" (Starts with an O(n) triangulation).

Given `n` points, determine if the Convex Hull is a hexagon (6 vertices).

O(n)

- "Run Gift-Wrapping for a constant number of steps".

"Ultimate" output-sensitive Convex Hull algorithm (Chan's algorithm).

O(n log h)

- "The best possible bound" (Know it exist

Geometric Primitive (e.g., Left, Area2, InCone)

O(1)

"Slow" Convex Hull (by testing all pairs for edges)

O(n³)

Basic Incremental Convex Hull (sorted by x-coordinate)

O(n²)

Trapezoidalization of a PSLG via Plane Sweep

O(n log n)

3-coloring the vertices of a triangulated n-gon

O(n)

Computing the Kernel of a simple polygon

O(n)

Computing g(P) (Point Guard Number) for a simple polygon

NP-hard

Computing w(P) (Witness Number) for a simple polygon

Polynomial T

Graham Scan

O(n log n)

Melkman's Algorithm

O(n)

Chazelle's Triangulation

O(n)

Plane Sweep Triangulation (for PSLG)

O(n log n)

Monotone Mountain Triangulation

O(n)

Textbook `Triangulate` (Ear Clipping)

O(n²)

Gift-Wrapping (Jarvis March)

O(nh)

QuickHull

O(nh)

Hertel-Mehlhorn Algorithm

O(n)

Chan's Convex Hull Algorithm

O(n log h)

Divide-and-Conquer Convex Hull

O(n log