Name
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 cur- rent number of vertices of the subdivision. Point lo- cation queries take O(log n) time, while updates take 0(log2 n) time. The space requirement is O(n log n). This is the first fully dynamic point location data struc- ture for monotone subdivisions that achieves optimal query time. |
Year | DOI | Venue |
|---|---|---|
1991 | 10.1145/109648.109655 | Symposium on Computational Geometry 2013 |
Keywords | Field | DocType |
planar point location,trapezoid method,point location | Topology,Combinatorics,Dynamization,Point location,Computer science,Planar | Conference |
ISBN | Citations | PageRank |
0-89791-426-0 | 7 | 0.72 |
References | Authors | |
15 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yi-jen Chiang | 1 | 503 | 38.21 |
| R Tamassia | 2 | 4686 | 550.39 |