DYNAMIZATION OF THE TRAPEZOID METHOD FOR PLANAR POINT LOCATION IN MONOTONE SUBDIVISIONS

作     者：Chiang, Yi-Jen Tamassia, Roberto 

作者机构：Brown Univ Dept Comp Sci Providence RI 02912 USA 

出 版 物：《INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS》 (国际计算几何学与应用杂志)

年 卷 期：1992年第2卷第3期

页      面：311-333页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Science Foundation [CCR-9007851] U.S. Army Research Office [DAAL03-91-G-0035] Office of Naval Research Project Agency [N00014-91-J-4052] Defense Advanced Research Project Agency [N00014-91-J-4052] 

主　　题：Computational geometry planar point location dynamic data structure monotone subdivision analysis of algorithms 

摘      要：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 other updates). 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.