Improved Dynamic Planar Point Location
Lars Arge, Gerth Stølting Brodal and
Loukas
Georgiadis
Abstract
We develop the
first linear-space data structures for dynamic planar point location in
general
subdivisions that achieve logarithmic query time and poly-logarithmic
update
time.
