next up previous contents index CD CD Algorithms
Next: Intersection Detection Up: Computational Geometry Previous: Range Search

Point Location



Input description: A decomposition of the plane into polygonal regions and a query point q.

Problem description: Which region contains the query point q?

Discussion: Point location is a fundamental subproblem in computational geometry, usually needed as an ingredient to solve larger geometric problems. In a dispatch system to assign policemen to the scene of a crime, the city will be partitioned into different precincts or districts.   Given a map of regions and a query point (the crime scene), the system must identify which region contains the point. This is exactly the problem of planar point location, variations of which include:

The simplest algorithm to guarantee tex2html_wrap_inline30150 worst-case access is the slab method, which draws horizontal lines through each vertex, thus creating n+1 ``slabs'' between the lines. Since the slabs are defined by horizontal lines, finding the slab containing a particular query point can be done using a binary search on the y-coordinate of q. Since there can be no vertices within any slab, looking for the region containing a point within a slab can be done by a second binary search on the edges that cross the slab. The catch is that a binary search tree must be maintained for each slab, for a worst-case of tex2html_wrap_inline30152 space if each region intersects each slab. A more space-efficient approach based on building a hierarchy of triangulations over the regions also achieves tex2html_wrap_inline30154 for search and is discussed in the notes below.  

Worst-case efficient computational geometry methods either require a lot of storage or are fairly complicated to implement. We identify implementations of worst-case methods below, which are worth at least experimenting with. However, we recommend kd-trees for most general point-location applications.

Implementations: LEDA (see Section gif) provides excellent support for maintaining planar subdivisions in C++ and, in particular, supports point location in tex2html_wrap_inline30156 time.    

Arrange is a package for maintaining arrangements of polygons in either the plane or on the sphere. Polygons may be degenerate, and hence represent arrangements of lines. A randomized incremental construction algorithm is used, and efficient point location on the arrangement is supported. Polygons may be inserted but not deleted from the arrangement, and arrangements of several thousand vertices and edges can be constructed in a few seconds. Arrange is written in C by Michael Goldwasser and is available from    

A routine in C to test whether a point lies in a simple polygon has been provided by O'Rourke [O'R94], and a Pascal routine for the same problem by [MS91]. For information on both, see Section gif.  

Notes: The inside-outside test for convex polygons is described in [PS85], which has a very thorough treatment of deterministic planar point location data structures. Expositions on the inside-outside test for simple polygons include [Man89, PS85].

An experimental study of algorithms for planar point location is described in [EKA84]. The winner was a bucketing technique akin to the grid file.   

The elegant triangle refinement method of Kirkpatrick [Kir83] builds a hierarchy of triangulations above the actual planar subdivision such that each triangle on a given level intersects only a constant number of triangles on the following level. Since each triangulation is a fraction of the size of the subsequent one, the total space is obtained by summing up a geometric series and hence is linear. Further, the height of the hierarchy is tex2html_wrap_inline30158 , ensuring fast query times. An alternative algorithm realizing the same time bounds is [EGS86]. The slab method described above is due to [DL76] and is presented in [PS85].

More recently, there has been interest in dynamic data structures for point location, which support fast incremental updates of the planar subdivision (such as insertions and deletions of edges and vertices) as well as fast point location. Chiang and Tamassia's [CT92] survey is an appropriate place to begin.  

Related Problems: Kd-trees (see page gif), Voronoi diagrams (see page gif), nearest neighbor search (see page gif).      

next up previous contents index CD CD Algorithms
Next: Intersection Detection Up: Computational Geometry Previous: Range Search

Mon Jun 2 23:33:50 EDT 1997