New results on dynamic planar point location

Siu Wing Cheng, Ravi Janardan

Research output: Contribution to journalConference articlepeer-review

4 Scopus citations

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 languageEnglish (US)
Pages (from-to)96-105
Number of pages10
JournalIEEE Transactions on Industry Applications
Volume27
Issue number1 pt 1
DOIs
StatePublished - Jan 1 1991
Event1989 Industry Applications Society Annual Meeting - San Diego, CA, USA
Duration: Oct 1 1989Oct 5 1989

Cite this