文章基本信息

标题：A Simple Dynamization of Trapezoidal Point Location in Planar Subdivisions
本地全文：下载
作者：Milutin Brankovic ; Nikola Grujic ; Andr van Renssen 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：168
页码：18:1-18:18
DOI：10.4230/LIPIcs.ICALP.2020.18
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We study how to dynamize the Trapezoidal Search Tree (TST) - a well known randomized point location structure for planar subdivisions of kinetic line segments. Our approach naturally extends incremental leaf-level insertions to recursive methods and allows adaptation for the online setting. The dynamization carries over to the Trapezoidal Search DAG (TSD), which has linear size and logarithmic point location costs with high probability. On a set S of non-crossing segments, each TST update performs expected ð'ª(logÂ² S ) operations and each TSD update performs expected ð'ª(log S ) operations. We demonstrate the practicality of our method with an open-source implementation, based on the Computational Geometry Algorithms Library, and experiments on the update performance.
关键词：Dynamization; Trapezoidal Search Tree; Trapezoidal Search DAG; Backward Analysis; Point Location; Planar Subdivision; Treap; Order-maintenance