Planar subdivisions and point location

A doubly connected edge list represents each undirected edge by two oppositely directed half-edges. Each half-edge records its twin, origin, next boundary edge, and incident face; suitable vertex and face records provide entry points. This supports local navigation around a face or vertex without repeatedly searching a geometric drawing. Holes and disconnected components need their own boundary-cycle records. The representation stores a planar embedding, not merely an abstract graph with no information about cyclic edge order.

For a finite connected plane graph, Euler's formula includes the unbounded face. More generally the right side depends on the number of connected components. These are useful consistency checks after splitting crossings or adding diagonals. They do not alone verify a correct embedding: overlapping edges, self-crossing face boundaries, or incorrect twin links can satisfy a numerical count. Incidence invariants and robust geometric predicates remain necessary. If original segments have many crossings, the stored subdivision can be quadratic in their initial count.

A vertical decomposition adds rays from vertices until they hit another edge or an enclosing box, producing constant-complexity trapezoid-like cells. A search hierarchy compares a query with vertical boundaries and supporting segments to locate its cell, then retrieves the original face label. The geometric decomposition and the hierarchy are different objects: many search paths may share a leaf for the same cell. A directed acyclic graph records that sharing and can remain much smaller than a naively duplicated search tree.

For noncrossing segment edges in a bounding box, with shared endpoints handled consistently and the usual generic sweep-direction assumptions, randomized incremental trapezoidal construction gives expected linear space and expected logarithmic search for each fixed interior query, with expected preprocessing at sorting scale. These expectations concern insertion order, independent of the fixed input and query, rather than a random query distribution. A worst-case bound simultaneously for all queries needs a stronger certified construction or another structure; it does not follow from the fixed-query expectation.

An orientation zero at an edge is a possible answer, not a failed comparison. For an edge-interior query, an API may return the edge and both incident faces; at a vertex, it may return the vertex and its incident features. A face-only API can choose a consistent half-open ownership convention instead, but must document it. Generic interior-query analysis often excludes vertical alignments with vertices; implementations handle these ties through explicit branches or symbolic comparisons rather than numerical nudges.

Keep preprocessing stages separate when reporting costs. Constructing an arrangement from intersecting input segments can dominate building a locator for the resulting subdivision. If the input is already a valid subdivision, that initial intersection work has already been done. A logarithmic query in the final complexity does not imply a subquadratic total representation for an arbitrary segment arrangement. Similarly, triangulating or vertically decomposing a region introduces auxiliary edges whose labels must preserve the original face identity.