TY - GEN
T1 - Dynamization of the trapezoid method for planar point location
AU - Chiang, Yi Jen
AU - Tamassia, Roberto
N1 - Publisher Copyright:
© 1991 ACM.
PY - 1991/6/1
Y1 - 1991/6/1
N2 - 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(logn) time, while updates take O(log2n) time. 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.
AB - 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(logn) time, while updates take O(log2n) time. 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.
UR - http://www.scopus.com/inward/record.url?scp=35248870583&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=35248870583&partnerID=8YFLogxK
U2 - 10.1145/109648.109655
DO - 10.1145/109648.109655
M3 - Conference contribution
AN - SCOPUS:35248870583
SN - 0897914260
T3 - Proceedings of the Annual Symposium on Computational Geometry
SP - 61
EP - 70
BT - Proceedings of the Annual Symposium on Computational Geometry
PB - Association for Computing Machinery
T2 - 7th Annual Symposium on Computational Geometry, SCG 1991
Y2 - 10 June 1991 through 12 June 1991
ER -