Page "Point location" Paragraph 23

It is not easy to see how to use a trapezoidal decomposition for point location, since a binary search similar to the one used in the slab decomposition can no longer be performed.

Instead, we need to answer a query in the same fashion as the triangulation refinement approach, but the data structure is constructed top-down.

Initially, we build a trapezoidal decomposition containing only the bounding box, and no internal vertex.

Then, we add the segments from the subdivision, one by one, in random order, refining the trapezoidal decomposition.

Using backwards analysis, we can show that the expected number of trapezoids created for each insertion is bounded by a constant.