TY - GEN

T1 - Dynamization of the trapezoid method for planar point location

AU - Chiang, Yi Jen

AU - Tamassia, Roberto

N1 - Funding Information:
*Research supported in part by the National Science Foundation under grant CCR-9007851, by the U.S. Army Research Office under grant DAAL03-91-G-O035, and by Cadre Technologies, Inc.
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 -