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:
“What we call little things are merely the causes of great things; they are the beginning, the embryo, and it is the point of departure which, generally speaking, decides the whole future of an existence. One single black speck may be the beginning of a gangrene, of a storm, of a revolution.”
—Henri-Frédéric Amiel (1821–1881)