Planar Case
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.
Read more about this topic: Point Location
Famous quotes containing the word case:
“In the case of a deliberate, palpable, and dangerous exercise of ... powers not granted by the compact, the States ... are in duty bound to interpose for arresting the progress of the evil, and for maintaining within their respective limits the authorities, rights, and liberties appertaining to them.”
—James Madison (1751–1836)