Planar Point Location

Edelsbrunner, Guibas and Stolfi

The method of Edelsbrunner, Guibas and Stolfi (1986) creates a subdivision L of a straight line graph with m edges and an associated data structure called a layered dag (directed acyclical graph). The data structure can be built in O(m) time, uses O(m) storage, makes point location queries in O(log m), and is thus optimal.

The technique involves generating a monotone subdivision. A monotone subdivision is a subdivision which has all individual regions (polygons) monotone, and no vertical edges. Each interval (a set of connected edges) in a monotone subdivision is said to be monotone if any vertical lines does not intersect that interval more than once. A polygon is monotone if its intersects a vertical line only once. Such a subdivision is shown below in figure 1.

Fig 1. A monotone subdivision of the plane and a valid separator (shown in red) of the subdivision.

A potentially non-monotone subdivision is transformed into a monotone one through a process known as regularization which adds edges (and therefore new regions) to the subdivision to ensure that each polygon is monotone. Then a set of separators are added. A separator (for example the red line in the figure above) is a polygonal line or chain consisting of edges and vertices of the subdivision which meets any vertical line drawn through the subdivision exactly once. Any element in L which is not part of the separator itself is either above or below it. A complete family of separators for a monotone subdivision is a set of separators such there is at least one region between each separator and separators do not intersect. The family of separators is used to partition the regions into a search tree like structure called a layered dag.