Overview
Trapezoidal map point location incrementally splits a planar segment subdivision into vertical trapezoids and records the decisions in a search DAG that routes later query points to their containing cell.
CoreSource checked
Trapezoidal Map Point Location
Locates a query point in a planar subdivision using a trapezoidal decomposition and search DAG.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Geometry
- Difficulty
- Intermediate
- Family
- Point Location
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 0
- Relationships
- 4
- Code example
- Ready
- Visualization
- Ready
Core Concepts
point locationtrapezoidal mapsearch DAGrandomized incremental constructionplanar subdivision
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(n log n)
Worst
O(n^2)
Space
O(n)
When to Use
- Use when the subdivision is mostly static and many point-location queries are expected.
- Use when input segments are noncrossing or have been split into a valid planar subdivision.
When Not to Use
- Avoid when degeneracies such as vertical segments, overlapping endpoints, or boundary queries are not handled.
- Avoid when frequent updates would make maintaining the search DAG more expensive than direct search.
What It Does
- Preprocesses a planar subdivision for repeated point-location queries.
- Splits regions into trapezoids bounded by vertical extensions and input segments.
- Uses a search DAG of x-coordinate and segment-side tests to locate query points.
Use Cases
- Repeated point-location queries in static maps, arrangements, or geometric subdivisions.
- Computational geometry teaching examples for randomized incremental construction.
- Preprocessing before geometric routing, visibility, or region-membership queries.
Inputs
- Points, segments, polygons, or geometric primitives
- Query or construction parameters
Outputs
- Geometric decision, measurement, or constructed structure
Pseudocode
- 1.Create a bounding box trapezoid
- 2.Insert subdivision segments in randomized order
- 3.Find trapezoids crossed by the inserted segment
- 4.Replace crossed trapezoids with the new split trapezoids
- 5.Update affected DAG leaves with x and segment-side decisions
- 6.Answer a query by following the DAG to a leaf trapezoid
Canonical Example
- Input
- a rectangle split by one horizontal segment, with query point q above the segment
- Output
- the upper trapezoid containing q
- Explanation
- The search DAG tests q against the segment and routes it to the leaf cell above it.
Implementation Notes
- Start with a bounding box and insert noncrossing segments in randomized order.
- For each inserted segment, find all intersected trapezoids and replace them with split cells.
- Represent DAG nodes as x-tests, segment-side tests, and leaf trapezoids.
Common Pitfalls
- The standard randomized analysis assumes careful incremental insertion and conflict tracking.
- Query points on segment boundaries or vertical walls need deterministic tie rules.
- Updating trapezoids without updating every affected DAG leaf leads to stale query answers.
Interactive Mechanism Walkthrough
Spatial Primitive & Sweep-Line CanvasShow decomposing a polygonal subdivision into searchable trapezoids on a small planar point location example.
Step 1 of 6: Create a bounding box trapezoid
geometry-mechanismNotes
The data structure is elegant but implementation-heavy; robust predicates and boundary conventions are essential.
Sources (2)
What each reference supports for this entry.
Computational Geometry: Algorithms and Applications
BookTextbook support for Trapezoidal Map Point Location's computational geometry problem family, predicates, structures, or geometric construction.
Open sourceThe Algorithm Design Manual
BookAlgorithm catalog support for planar point location and computational geometry tradeoffs.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Alternative toKirkpatrick Point Location
Geometry · Specialized
Both preprocess planar subdivisions for point-location queries using different structures.
Compare with thisRelationships
View full relationship pageAlternative toKirkpatrick Point Location
Both preprocess planar subdivisions for point-location queries using different structures.
GeneralizesPoint in Polygon
Planar point location can identify a containing subdivision cell, while point-in-polygon answers a single-region containment question.
Alternative toPoint Location in Triangulation
Trapezoidal maps and triangulation walking answer related point-location queries with different preprocessing assumptions.
Tags
GeometryComputational Geometry