Abstract
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(log2n) 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(log2n 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.
Original language | English (US) |
---|---|
Pages (from-to) | 96-105 |
Number of pages | 10 |
Journal | IEEE Transactions on Industry Applications |
Volume | 27 |
Issue number | 1 pt 1 |
DOIs | |
State | Published - Jan 1991 |
Event | 1989 Industry Applications Society Annual Meeting - San Diego, CA, USA Duration: Oct 1 1989 → Oct 5 1989 |