# 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.

##### MSC:
 68U05 Computer graphics; computational geometry (digital and algorithmic aspects) 68P10 Searching and sorting 68Q25 Analysis of algorithms and problem complexity
##### Keywords:
dynamic planar point location problem
Full Text: