The site's eleven Geometry entries don't compete for the same job the way the ten Convex Hull entries do (that family gets its own guide, and its own entries all compute the identical hull by different mechanisms). These eleven answer three genuinely different questions instead, and most of them split further into a one-off version and a repeated-query or find-them-all version of the same question. So this guide asks three things in order, cheapest to place first:
If it's asked once, or a handful of times, against a polygon that might change between
queries, Point in Polygon's ray-casting test
answers it directly in O(n) time and O(1) space, no setup required —
walk every edge once, count crossings, done. It handles convex and concave polygons identically
and needs nothing built in advance. That answer assumes the polygon is simple — its own boundary
never crosses itself. If it might not be, Winding Number Algorithm answers the same
question at the same O(n)/O(1) cost, just by keeping the direction of
each crossing instead of only its parity; on a simple polygon the two always agree, and the extra
bookkeeping only earns its keep once a region can be enclosed more than once.
If the same fixed polygon is going to answer many later queries, paying a
preprocessing cost once to answer each later query in O(log n) instead of rescanning
every edge is worth it — and here the site has two entries answering the same follow-up question
with the same query bound but different preprocessing risk.
Slab Decomposition is the simpler build: extend a
vertical boundary from every vertex, slicing the plane into slabs, then answer any later query with
two binary searches (which slab, then which edge within it) — always O(log n), no
matter where the point lands. The catch is its preprocessing cost, which its own page built and
measured directly rather than just citing the bound: a polygon with thin teeth staggered so no two
vertices share an x-coordinate forces almost every slab to hold almost every edge — at
n = 132 vertices, 1,122 total (slab, edge) pairs; at n = 260, 4,290 pairs,
the pairs-per-n ratio nearly doubling alongside n itself, the real
signature of O(n²) growth, not a constant-factor artifact. Trapezoidal Map is the fix for exactly that failure
mode: insert the same edges one at a time in random order instead of building every slab
up front, merging neighboring regions into trapezoids as it goes. The randomization is load-bearing,
not cosmetic — it's what turns an adversary's ability to pick a bad polygon into an
expectation over the algorithm's own coin flips, bringing preprocessing down to O(n log
n) expected time (this build's simpler DAG-only search structure costs slightly more,
O(n log² n) expected) and O(n) expected space, while keeping the same
O(log n) query — now expected rather than always, since an unlucky random order is
still possible, just no longer forced by the input. Its own demo measured the query side directly:
19 trapezoids built from 7 edges, averaging 3.7 search steps and never exceeding 8 across 5,000
random query points, against log₂ 19 ≈ 4.2. Reach for Slab Decomposition when the
polygon is small or trusted not to be adversarial and the simpler build is worth it; reach for
Trapezoidal Map when the polygon could be large or hostile and the preprocessing guarantee
actually matters.
For one specific pair, Line Segment
Intersection's orientation test answers it in flat O(1) — four cross-product
evaluations, no sorting, no recursion, no dependence on any other segment in the scene, the only
entry in either this category or Convex Hull with that property. For n segments,
asking which pairs among all of them cross turns into a genuinely different, harder
problem: repeating the O(1) test on every pair is O(n²), and doing
better needs a different algorithm built on top of it. Bentley–Ottmann is that algorithm — sweep a vertical
line across the plane, maintaining only the segments currently crossing it in order, and test a
pair only once they become adjacent in that order. It finds every intersection in
O((n + k) log n), where k is the number found — genuinely better than
brute force whenever k is small relative to n², which is the case it's
built for. Its own Complexity section is honest that this isn't unconditional: push
k up toward its n² ceiling — nearly every pair genuinely crossing — and
the bound degrades to O(n² log n), asymptotically worse than the brute-force
approach it's meant to improve on. Reach for the O(1) test alone when there's one
pair to check; reach for the sweep only when the segment count is large and intersections are
expected to be the exception, not the rule.
Three different starting shapes, then two of the three share a duality that changes which one to build.
If what's given is a simple polygon's own boundary and the goal is to tile its
interior — every downstream consumer that actually wants triangles, not an arbitrary
polygon, from GPU rasterization to a physics engine's convex-piece assumption —
Polygon Triangulation (ear clipping) is the
direct route: repeatedly find a convex vertex no other vertex intrudes on, clip it off as a
triangle, repeat. Its own page measures the straightforward version at O(n²) (each of
n − 2 clips does an O(n) containment scan); a monotone-decomposition
approach brings the worst case down to O(n log n), and a genuinely linear algorithm
exists but is complex enough it's essentially never used.
If what's given is a bare point set with no boundary at all, the connectivity has to
be invented rather than cut from an existing shape — a fundamentally different starting problem,
even though the output is triangles either way. Delaunay Triangulation answers it by a specific
rule (no point ever sits inside another triangle's circumcircle) that turns out to avoid the thin
sliver triangles that make mesh interpolation and nearest-neighbor queries behave badly. Its own
Bowyer-Watson implementation costs O(n²) (each of n insertions scans
every current triangle); randomizing the insertion order and adding a point-location structure —
the same trick behind Trapezoidal Map above — brings the expected cost to O(n log
n), the real-world standard.
A Delaunay triangulation carries a second structure for free: connect the circumcenters of
every pair of triangles sharing an edge, and the result is the Voronoi Diagram of the same points — the partition of
the plane into "closest to this site" regions. This site's own Voronoi Diagram page builds each
cell independently instead of reusing that structure, deliberately, to make the duality check a
genuine cross-check rather than reused work — and pays for it at O(n³) (each of
n cells clips against n − 1 half-planes, each clip O(n)).
Two cheaper real routes exist: read the dual straight off an already-built Delaunay mesh in
O(n), or skip Delaunay altogether and build the Voronoi diagram directly with Fortune's Algorithm, sweeping a line down the plane
and maintaining a "beach line" of parabolic arcs, in O(n log n) — the standard
real-world approach for exactly this question. Reach for Polygon Triangulation when a boundary
already exists and needs cutting; reach for Delaunay when the input is a bare point set and
triangles themselves are the goal; reach for Voronoi (via Delaunay's dual, or directly via
Fortune's) when nearest-site regions, not triangles, are what's actually needed.
Closest Pair of Points asks a related but
distinct question against the same kind of bare input — not how to triangulate or partition the
plane, just which two points are nearest each other — and doesn't fit the triangulation/duality
pair above at all; it's included in this question because it shares the same "bare point set, no
boundary" starting shape, not because it competes with Delaunay or Voronoi for the same job. Its
divide-and-conquer approach has the identical recursion shape as Merge Sort — split, recurse on each half, merge
through a narrow strip that might hide the real answer straddling both halves — landing on the
same O(n log n) for the same reason. Its own demo measured the payoff directly on 12
points: 66 pairwise comparisons for brute force, versus 23 total (12 base-case plus 11
strip-check) for the divide-and-conquer version.
| Entry | Time | Space | Answers | Reach for it when |
|---|---|---|---|---|
| Point in Polygon | O(n) per query | O(1) | is this point inside this polygon? | one-off or few queries, no preprocessing wanted |
| Winding Number Algorithm | O(n) per query | O(1) | is this point inside this polygon, even if it self-intersects? | the polygon might not be simple |
| Slab Decomposition | O(log n) query, always; O(n²) worst-case preprocess | O(n²) worst case | same, repeated against a fixed polygon | many queries, simple build, polygon isn't adversarial |
| Trapezoidal Map | O(log n) query, expected; O(n log n) expected preprocess | O(n) expected | same, with a worst-case-resistant build | many queries, polygon could be large or hostile |
| Line Segment Intersection | O(1) | O(1) | do these two specific segments cross? | checking one pair |
| Bentley–Ottmann | O((n + k) log n) | O(n + k) | which pairs among n segments cross? | many segments, few expected intersections |
| Polygon Triangulation | O(n²) (O(n log n) with monotone decomposition) | O(n) | tile a fixed polygon's interior into triangles | a boundary already exists and needs cutting |
| Delaunay Triangulation | O(n²) naive; O(n log n) expected with point location | O(n) | triangulate a bare point set, avoiding sliver triangles | the input is only points, no boundary, and triangles are the goal |
| Voronoi Diagram | O(n) from an existing Delaunay mesh; O(n³) built from scratch | O(n) (O(n²) worst case built cell-by-cell) | partition the plane into nearest-site regions | a Delaunay triangulation already exists to read the dual from |
| Fortune's Algorithm | O(n log n) | O(n) | same, without building Delaunay first | nearest-site regions are the goal and Delaunay isn't needed for anything else |
| Closest Pair of Points | O(n log n) | O(n) | which two points, out of n, are nearest each other? | a bare point set, the question is distance not connectivity |