zbMATH — the first resource for mathematics

Dynamic point location in general subdivisions. (English) Zbl 0820.68122
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:
\(\bullet\) Locate (\(q\): point): Report the segment immediately above \(q\), i.e., the first segment intersected by an upward vertical ray starting at \(q\);
\(\bullet\) Insert (\(s\): segment): Add segment \(s\) to the collection \(S\) of segments;
\(\bullet\) Delete (\(s\): segment): Remove segment \(s\) from the collection \(S\) 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.

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68P10 Searching and sorting
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI