Dynamic trees and dynamic point location
Michael T. Goodrich, Roberto Tamassia · 1991
ResultsWe give new methods for maintaining a pointlocation data structure for a dynamically-changing monotone subdivision S. Our approa,ch is based on a new, optimal static point-location structure, where one represents $ via two int erlaced spanning trees, one for S and one for the graph-theoretic dual of S. Queries are answered by using a centroid decomposition of the dual tree to drive searches in the primal tree.We maintain these trees via the link-cut trees structure of Sleator and Tarjan, leading to a scheme that achieves vertex