History


Please fill in your query. A complete syntax description you will find on the General Help page.
Dynamic point location in general subdivisions. (English)
J. Algorithms 17, No.3, 342-380 (1994).
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\sp 2 n)$. The bounds for insertions and deletions are amortized. A query time below $O(\log\sp 2 n)$ was previously only known for monotone subdivisions and subdivisions consisting of horizontal segments and required nonlinear space.
WorldCat.org
Valid XHTML 1.0 Transitional Valid CSS!