Rounding arrangements dynamically

作     者：Guibas, LJ Marimont, DH 

作者机构：Stanford Univ Dept Comp Sci Stanford CA 94305 USA Xerox Corp Palo Alto Res Ctr Palo Alto CA 94304 USA 

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

年 卷 期：1998年第8卷第2期

页      面：157-178页

核心收录：

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

主　　题：arrangement vertical trapezoidal decomposition dynamic data structure randomized algorithm robustness rounding 

摘      要：We describe a robust, dynamic algorithm to compute the arrangement of a set of line segments in the plane, and its implementation. The algorithm is robust because, following Greene(7) and Hobby,(11) it rounds the endpoints and intersections of all line segments to representable points, but in a way that is globally topologically consistent. The algorithm is dynamic because, following Mulmuley,(16) it uses a randomized hierarchy of vertical cell decompositions to make locating points, and inserting and deleting line segments,, efficient. Our algorithm is novel because it marries the robustness of the Greene and Hobby algorithms with Mulmuley s dynamic algorithm in a way that preserves the desirable properties of each.