Point location

The point location problem is a fundamental topic of computational geometry. It finds applications in areas that deal with processing geometrical data: computer graphics, geographic information systems (GIS), motion planning, and computer aided design (CAD). The point location problem is a fundamental topic of computational geometry. It finds applications in areas that deal with processing geometrical data: computer graphics, geographic information systems (GIS), motion planning, and computer aided design (CAD). In its most general form, the problem is, given a partition of the space into disjoint regions, to determine the region where a query point lies. As an example application, each time one clicks a mouse to follow a link in a web browser, this problem must be solved in order to determine which area of the computer screen is under the mouse pointer. A simple special case is the point in polygon problem. In this case, we need to determine whether the point is inside, outside, or on the boundary of a single polygon. In many applications, we need to determine the location of several different points with respect to the same partition of the space. To solve this problem efficiently, it is useful to build a data structure that, given a query point, quickly determines which region contains the query point (e.g. Voronoi Diagram). In the planar case, we are given a planar subdivision S, formed by multiple polygons called faces, and need to determine which face contains a query point. A brute force search of each face using the point-in-polygon algorithm is possible, but usually not feasible for subdivisions of high complexity. Several different approaches lead to optimal data structures, with O(n) storage space and O(log n) query time, where n is the total number of vertices in S. For simplicity, we assume that the planar subdivision is contained inside a square bounding box. The simplest and earliest data structure to achieve O(log n) time was discovered by Dobkin and Lipton in 1976. It is based on subdividing S using vertical lines that pass through each vertex in S. The region between two consecutive vertical lines is called a slab. Notice that each slab is divided by non-intersecting line segments that completely cross the slab from left to right. The region between two consecutive segments inside a slab corresponds to a unique face of S. Therefore, we reduce our point location problem to two simpler problems: The first problem can be solved by binary search on the x coordinate of the vertical lines in O(log n) time. The second problem can also be solved in O(log n) time by binary search. To see how, notice that, as the segments do not intersect and completely cross the slab, the segments can be sorted vertically inside each slab. While this algorithm allows point location in logarithmic time and is easy to implement, the space required to build the slabs and the regions contained within the slabs can be as high as O(n²), since each slab can cross a significant fraction of the segments. Several authors noticed that the segments that cross two adjacent slabs are mostly the same. Therefore, the size of the data structure can be significantly reduced. More specifically, Sarnak and Tarjan sweep a vertical line l from left to right over the plane, while maintaining the segments that intersect l in a Persistent red-black tree. This allows them to reduce the storage space to O(n), while maintaining the O(log n) query time. A (vertical) monotone chain is a path such that the y-coordinate never increases along the path. A simple polygon is (vertical) monotone if it is formed by two monotone chains, with the first and last vertices in common. It is possible to add some edges to a planar subdivision, in order to make all faces monotone, obtaining what is called a monotone subdivision. This process does not add any vertices to the subdivision (therefore, the size remains O(n)), and can be performed in O(n log n) time by plane sweep (it can also be performed in linear time, using polygon triangulation). Therefore, there is no loss of generality, if we restrict our data structure to the case of monotone subdivisions, as we do in this section.