New results on dynamic planar point location

A point location scheme is presented for an n-vertex dynamic planar subdivision whose underlying graph is only required to be connected. The scheme uses O(n) space and yields an O(log²n) query time and an O(log n) update time. Insertion [respectively, deletion] of an arbitrary k-edge chain inside a region can be performed in O( k log(n+k)) [respectively, O(k log n)] time. The scheme is then extended to speed up the insertion/deletion of a k-edge monotone chain to O(log ²n log log n+k) time [or O(log n log log n+k) time for an alternative model of input], but at the expense of increasing the other time bounds slightly. All bounds are worst case. Additional results include a generalization to planar subdivisions consisting of algebraic segments of bounded degree and a persistent scheme for planar point location