Name
Title | ||
|---|---|---|
Dynamization of the Trapezoid Method for Planar Point Location in Monotone Subdivisions |
Abstract | ||
|---|---|---|
We present a fully dynamic data structure for point location in a monotone subdivision, based on the trapezoid method. The operations supported are insertion and deletion of vertices and edges, and horizontal translation of vertices. Let $n$ be the current number of vertices of the subdivision. Point location queries take $O(\log n)$ time, while updates take $O(\log^2 n)$ time (amortized for vertex insertion/deletion and worst-case for the others). The space requirement is $O(n \log n)$. This is the first fully dynamic point location data structure for monotone subdivisions that achieves optimal query time. |
Year | DOI | Venue |
|---|---|---|
1992 | 10.1142/S0218195992000184 | Int. J. Comput. Geometry Appl. |
Keywords | DocType | Volume |
log n,monotone subdivision,dynamic point location data,optimal query time,point location,point location query,dynamic data structure,vertex insertion,current number,horizontal translation,Monotone Subdivisions,Planar Point Location,Trapezoid Method | Journal | 2 |
Issue | ISSN | Citations |
3 | 0218-1959 | 7 |
PageRank | References | Authors |
0.53 | 16 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yi-jen Chiang | 1 | 503 | 38.21 |
| R Tamassia | 2 | 4686 | 550.39 |