Lecture
Given a planar straight-line graph (PSLG) and a certain point P. We need to locate the point within the PSLG (determine above/below which edge of the PSLG this point is situated).
Let's draw a vertical line through each vertex. We get strips (slabs). Let each strip correspond to the point through which the left edge of the strip is drawn. We will store a sorted array of x -coordinates, then in O(logn) we can find which strip P lies in.
Point Location
Within each strip, the segments making up the PSLG can only intersect at their endpoints, and these intersection points can only lie on the lines bounding the strips (by construction). It follows that within each strip we can sort the segments that lie in it, for example from bottom to top. Then, having found the required strip, we can quickly find the required segment.
One-Dimensional Problem
Persistent data structures are structures that, God save the Tsar, store the history of their changes. Persistence can be full (when we can modify any version) or partial (when we can only modify the latest version, but can make queries on all of them).
One way to make a tree partially persistent is node-copying (or path-copying, as it is called differently in different sources). We store an array of tree roots. When we need to modify a node, we create a new root in this array, but its left and right fields coincide with those in the previous root. We then go from the root to the node we want to modify. We «copy» all the vertices along the path in the same way as the root, changing the corresponding pointer in the parent to the new one. After that, we change the node we need. Thus, for such a tree we need O(nlogn) memory.
This method can be improved. Now each node will store a version number and fields for lazy modification of the tree: a fixed number of spare left and right pointers, and version numbers for them. When we want to modify a node, instead of copying, we write the changes into the spare pointers, if there are still any available; otherwise we create a new node and correspondingly fix its parent. We use binary search to search across versions. This method is called limited node copying; it requires O(n) memory, because on an amortized basis we copy O(1) nodes per update.
We will use a balanced partially persistent tree to store the segments within the strips. Each strip is a new version of the tree.
A query requires O(logn) , preprocessing requires O(nlogn) ; memory requires O(n) .
Comments