Planar Point Location

Introduction

The problem of planar partitioning and planar point location is a fundamental problem in computational geometry. The problem may defined as the preprocessing of a polygonal subdivision of the plane into some data structure such that it is possible to efficiently query into which polygon a query point falls (Arya, Malamatos, & Mount, 2000). Such queries are very common in applications such as Geographical Information Systems (GIS). Consider for example a user viewing a digital map of the world on a computer monitor and the user wishes to select a specific country for further investigation. The user clicks on the computer monitor inside the polygon representing that country and based on the screen coordinates and the information stored in the map the computer is able to determine which polygon the query point was inside and return the appropriate information to the user.

The planar partitioning step produces a subdivision of the plane that has a more regular partitioning thereby speeding up queries. For example a very simple, and fast data structure, might be to subdivide the plane into a grid of square cells such that the cells are small enough to represent all the detail inherent in the polygonal map. This is basically how raster maps are stored and point location queries can be performed in constant time, however, the storage requirements are so high that they render such an approach infeasible. The idea of planar partitioning is to create a data structure that will provide fast query times while not increasing the storage requirements for the polygonal data too much.

de Berg et al. (2000) have indicated that the optimal storage and search time for the PPL problem is O(n) for storage and O(log n) for search. They outline four differing approachs that have been able to successfully achieve these worst-case bounds these include:

• chain method of Edelsbrunner et al. (1986) based on segment trees and fractional cascading,
• the triangulation refinement method of Kirkpartick (1983),
• the use of persistent search trees by Sarnak and Tarjan (1986), and
• randomized construction of trapezoidal maps based the work of Mulmuley (1990) and Seidel (1991).

Planar point location is still an active field in computational geometry and a few recent papers will be introduced here though they by no means constitute a exhaustive survery of recent research, they are given primarily as examples of current research in the area. Arya, Malamatos, and Mount (2000) developed a BSP tree based method requiring O(n log n) storage but which had better than O( log n) expected-case query time. Arge and Vahrenhold (2002) present what they claim to be the first I/O efficient data structure for point location using fractional cascading to produce a structure using O(N/B) disk blocks where B is the size of a disk block. Their method allows queries in (O log2 N) and allows for efficient insertions and deletions into the planar subdivision. Finally, Iacono and Langerman (2003) described a data structure performing planar point location quickly in cases where a given query point is close to the previous query point in O( log d(q-1, q)) query time (where d(q-1, q) is the distance between the current and previous queries). Their data structure requires O( n log log n) space.

Outline

This website presents information on the four main methods for planar point location with a special emphasis on generation of trapezoidal maps following the method of Seidel (1990). Each of the three point location strategies named above, those of Edelsbrunner, Kirkpatrick and Sarnak and Trajan are all briefly discussed. The of random incremental method of Seidel as presented in de Berg(2000) is covered in detail and an interactive applet is included demonstrating the creation of trapezoid maps and queries on trapezoidal maps.