Dynamic Point Location in General Subdivisions

The dynamic planar point location problem is the task of maintaining a dynamic set S of n nonintersecting (except possibly at endpoints) line segments in the plane under the following operations: • Locate (: point): Report the segment immediately above , i.e., the first segment intersected by an upw...

Full description

Saved in:
Bibliographic Details
Published in:Journal of algorithms 1994-11, Vol.17 (3), p.342-380
Main Authors: Baumgarten, N., Jung, H., Mehlhorn, K.
Format: Article
Language:English
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The dynamic planar point location problem is the task of maintaining a dynamic set S of n nonintersecting (except possibly at endpoints) line segments in the plane under the following operations: • Locate (: point): Report the segment immediately above , i.e., the first segment intersected by an upward vertical ray starting at ; • Insert (: segment): Add segment to the collection of segments; • Delete (: segment): Remove segment from the collection of segments. We present a solution which requires space O( n) and has query and insertion time O(log n log log n) and deletion time O(log 2 n). The bounds for insertions and deletions are amortized. A query time below O(log 2 n) was previously only known for monotone subdivisions and subdivisions consisting of horizontal segments and required nonlinear space.
ISSN:0196-6774
1090-2678
DOI:10.1006/jagm.1994.1040