Point Location in $O(\log n)$

Problem: you have a planar subdivision (no degree-0/1 vertices) and many query points. For each query, report which face contains it. We answer all queries offline in O(log n) each (after sorting), via a sweep line.

Typical uses: locate points in a Voronoi diagram or inside a simple polygon’s trapezoidalization / DCEL.

This lesson follows CP-Algorithms — Point location.

Related: Basic Geometry, Half-plane Intersection.

Reduction: find a supporting edge

For query p = (x₀, y₀) find an edge e such that:

• if p lies on some edge, e is that edge; otherwise
• e intersects the vertical line x = x₀ at (x₀, y) with y < y₀, and this y is maximal among such edges.

If no such edge exists, p is in the outer face.

If p is not on e, the face is the one immediately above e (for non-vertical e). That face can be precomputed from a CCW face walk: when traversing e left→right (x increases), the face on the “walking” side is the one above.

Offline sweep

Collect all x-coordinates of query points and edge endpoints. Sweep left → right. Maintain:

• t — ordered set of active non-vertical edges (cover the current x)
• vert — vertical edges at the current x only (cleared each x)

Events (per x, sorted by type)

Order: VERT → GET → DEL → ADD.

Type	When
VERT	Vertical edge at this x
GET	Query with this x
DEL	Non-vertical edge ends (max endpoint x)
ADD	Non-vertical edge starts (min endpoint x)

Processing:

1. VERT — insert min endpoint y into vert
2. ADD / DEL — insert / erase edge in t
3. GET — binary search vert (point on vertical segment?); else upper_bound in t with a dummy edge at the query point to get the highest edge below

Degenerate fix: after finishing all events at this x, re-run GETs against the updated t and keep the better answer (handles cases like querying a left corner of a triangle).

Edge comparator for t

edge_cmp(e1=(a,b), e2=(c,d)) must say whether e1 stays below e2 on their common x-range:

val = sgn((b−a)×(c−a)) + sgn((b−a)×(d−a))
if val ≠ 0: return val > 0
val = sgn((d−c)×(a−c)) + sgn((d−c)×(b−c))
return val < 0

(Cross products with integer coordinates — no floats required.)

Complexity

Sorting events: O((n+q) log(n+q)). Each insert/erase/query on t / vert: O(log n). Total O((n+q) log(n+q)), i.e. O(log n) per query offline.

Online: the same idea works with a persistent ordered set of active edges across x.

From edge to face (DCEL sketch)

Store the subdivision as a DCEL. For each non-vertical undirected edge, remember which incident face is “above”. After sweepline returns an edge pointer:

• nullptr → outer face (-1)
• point on the segment → report on edge
• else → report the precomputed above face

🧪 Supporting edge under a query (toy sweep)

Reference: edge_cmp, sweep sketch, DCEL face map

Full integer DCEL version from CP-Algorithms. Outer face is -1. Each query returns (1, face) if strictly inside, or (0, edgeIndex) if on an edge.

// Comparator for active non-vertical edges in set t
bool edge_cmp(Edge* edge1, Edge* edge2) {
    const pt a = edge1->l, b = edge1->r;
    const pt c = edge2->l, d = edge2->r;
    int val = sgn(a.cross(b, c)) + sgn(a.cross(b, d));
    if (val != 0) return val > 0;
    val = sgn(c.cross(d, a)) + sgn(c.cross(d, b));
    return val < 0;
}

enum EventType { VERT = 0, GET = 1, DEL = 2, ADD = 3 };

// sweepline(planar edges, queries) → supporting Edge* per query
// At each x: sort events VERT→GET→DEL→ADD; maintain t and vert;
// GET: check vert, else upper_bound in t; re-GET after all events.

// point_location(DCEL, queries):
//   Build undirected edges; store "above" face when walking L→R (x increases).
//   If res[i]==nullptr → (1,-1); else if on segment → (0,edge); else (1,aboveFace).

Assumes the subdivision is a valid DCEL (twin / next / face). Persistent trees on t make the same status structure answer queries online.

Check: point location

Quiz

Point location

1 / 4

The geometric key per query is…

Pick an answer to see if you are right.

Practice drills

Activity: Event type order

Map names to rank used in the sweep: VERT=0, GET=1, DEL=2, ADD=3.
Input: a word (VERT/GET/DEL/ADD). Print its integer rank.

Practice problems

From CP-Algorithms:

• TIMUS 1848 — Fly Hunt
• UVA 12310 — Point Location (vjudge)

Cheat sheet

Idea	Takeaway
Goal	Face of planar subdivision for each query
Key	Highest edge ≤ query on x = x₀
Sweep	Events VERT / GET / DEL / ADD
Status	Set t + temp vert
Order	edge_cmp via cross signs
Face	Above supporting edge (CCW walk)
Time	Offline O((n+q) log(n+q))
Online	Persistent tree on t