Planar Point Location Using Persistent Search Trees
Report ID: TR-005-85Author: Sarnak, Neil / Tarjan, Robert E.
Date: 1985-07-00
Pages: 26
Download Formats: |PDF|
Abstract:
The planar point location problem is that of preprocessing a polygonal subdivision of the plane so that, given a sequence of points, the polygon containing each point can be determined quickly. Several ways of solving this problem in O(log n) query-time and O(n)-space are known, but they are all rather complicated. We propose a simple O(log n)-query time, O(n)-space solution, using persistent search trees. A persistent search tree differs from an ordinary search tree in that after an insertion or deletion, the old version of the tree can still be searched. We develop a persistent form of binary search tree that supports insertions and deletions in the present version and queries in any version, past or present. The time per query or update is O(log m), where m is the total number of updates, and the space needed is O(1) per update. Our planar point location algorithm is an immediate application of this data structure.