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.
Other articles related to "point location":
... There are no known general point location data structures with linear space and logarithmic query time for dimensions greater than 2 ... In three-dimensional space, it is possible to answer point location queries in O(log² n) using O(n log n) space ... The general idea is to maintain several planar point location data structures, corresponding to the intersection of the subdivision with n parallel planes that contain ...
Famous quotes containing the word point:
“When we are in love, the sentiment is too great to be contained whole within us; it radiates out to our beloved, finds in her a surface which stops it, forces it to return to its point of departure, and it is this rebound of our own tenderness which we call the others affection and which charms us more than when it first went out because we do not see that it comes from us.”
—Marcel Proust (18711922)