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:
“It is often the case that the man who can’t tell a lie thinks he is the best judge of one.”
—Mark Twain [Samuel Langhorne Clemens] (1835–1910)