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, determine the region where a query point lies. As an example application, each time you click 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.
Read more about Point Location: Planar Case, Higher Dimensions
Famous quotes containing the word point:
“In order to really enjoy a dog, one doesn’t merely try to train him to be semihuman. The point of it is to open oneself to the possibility of becoming partly a dog.”
—Edward Hoagland (b. 1932)