Technical Reports

The ICICS/CS Reading Room

UBC CS TR-81-13 Summary

Optimal Search in Planar Subdivisions, January 1981 David G. Kirkpatrick

A planar subdivision is any partition of the plane into (possibly unbounded) polygonal regions. The subdivision search problem is the following: given a subdivision $S$ with $n$ line segments and a query point $p$, determine which region of $S$ contains $p$. We present a practical algorithm for subdivision search that achieves the same (optimal) worst case complexity bounds as the significantly more complex algorithm of Lipton and Tarjan, namely $O(\log n)$ search time with $O(n)$ storage. Our subdivision search structure can be constructed in linear time from the subdivision representation used in many applications.

If you have any questions or comments regarding this page please send mail to