Point location

_Point location problem 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. For example, the problem of determining which window of a graphical user interface contains a given mouse click can be formulated as an instance of point location, with a subdivision formed by the visible parts of each window, although specialized data structures may be more appropriate than general-purpose point location data structures in this application. Another special case is the point in polygon problem, in which one needs to determine whether a point is inside, outside, or on the boundary of a single polygon. In many applications, one needs 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.