Planar point location is the problem of quickly determining which polygon each of a series of queries is in. Imagine throwing darts at the horrible mess to the right, how could you quickly search for what they hit? Because there are potentially many queries, we want to preprocess the graph to ensure fast querying with minimal memory overhead. The algorithm here (first presented by Sarnak, N., & Tarjan, R. E. (1986). Planar point location using persistent search trees. Communications of the ACM, 29(7), 669-679.), is to store the edges of the planar graph in a partially persistent binary search tree. Because it is a BST, queries and updates can be done in O(logn) time, and thanks to a fancy trick and amortized analysis the entire tree only requires O(n) space.
The key insight of this approach is to treat one dimension (of the 2D point location problem) as time. That is, instead of thinking of line segments in the planar graph as being line segments, think of them as the path taken by a moving point over a finite duration. In this view, one end of the line segment represents where and when the point came into being and the other end represents when the point blinked out of existence forever. Queries take on a temporal flavor as well, they amount to simply asking where would a given 1D point fall in the tree if it was queried at a given time in the tree's history.
The challenge then becomes, how can we build a search tree that respects the behavior of time? To simplify the problem, note that changes to the data structure will only occur at vertices of the graph. During intermediate times the points stored in the tree will move, but because the graph is planar they will never cross, so the only modification that is required is to store the slope (if you're thinking in 2 spatial dimensions, otherwise think of it as storing the point's speed) of each edge in the tree along side the starting point (and a modification to use that information when searching). If the queries were guaranteed to come in order we'd be done, we could maintain an ephemeral (ie non-persistent) search tree as we query, adding and removing edges as we proceed chronologically through the list of queries. Unfortunately this is one assumption that we cannot make, so we'll need to give our search tree some memory by making it persistent. [the binary search tree for a query at some point in the middle slab]
Data structures are called persistent when all of their past states can still be accessed via a time parameter. To take the most popular example, version control systems store changing data, but they are persistent because you can always revert to previous versions of their contents. They work by maintaining a collection of head pointers with timestamps, where each item pointed to by the head may have been edited at the current time or any previous time. When an item is added or removed the search path from the current head to the new (or old) node is copied except that the copy reflects the addition or removal, the head of the copied path is associated with the time of the modification and added to the collection of heads.
In our case we're using a binary search tree that has been modified to be partially persistent, which is to say that only the most recent head can be modified, because it allows for a better space bound. The space savings is achieved by not copying the entire O(logn) search path with each modification. Instead to each node we add a third pointer and a timestamp, and when it comes time to modify one of the node's children the pointer to the new child is stored in the third pointer slot and the timestamp at which the modifiation took place is recorded as well. If the third pointer is already used (so an update would require a fourth pointer), the node's contained edge is instead copied into a new node that points to the appropriate children nodes and has an empty third pointer. This limited node copying drops the amortized space cost of a modification to O(1) (which is intuitive since restoring the invariants after modifying an ephemeral red black tree requires O(1) pointer changes), so the overall space is O(n) for n edges.
So, with all of that in mind, when you draw a planar graph above and click Toggle Query Mode, here's what happens. Behind the scenes when you click the button each edge is paired with a start time, and again with a stop time, these 2n events are then sorted chronologically (that is, by horizontal coordinate of the event (point) in the graph) and applied to a partially persistent red black tree. Then, as you move the mouse across the graph it draws the tree as it existed at the time corresponding to the position of the cursor. The horizontal parts of the curvy tree intersect with the edges that that node of the tree represents.
When your mouse crosses a slab boundary the displayed tree changes. If the vertex that caused the slab boundary faces right, like a '<' then the tree will reflect the two new edges being inserted into it. If it faces left, like '>' then the tree will reflect two edges being deleted from it, and similarly if it faces up or down (like a 'v' or '^') the tree will reflect one deletion and one insertion. All this together, at any given time the tree contains every edge that crosses the slab that contains the query point.
For each query two binary searches are run: the first is a binary search through time to determine which slab (delineated by the vertical gray lines) contains the query (cursor). These slabs represent the insertions and deletions, which is to say, if the binary search tree were fully persistent the slabs would correspond with the O(n) heads of the tree. The second binary search is then searching within the tree as it existed during the slab (of time) to locate the highest edge below the query point. Given the highest edge below the query it's easy to determine which polygon contains the query: just associate with each edge the identity of the polygon it constitutes a lower edge of.