A Simple Dynamization of Trapezoidal Point Location in Planar Subdivisions

Autor:	Brankovic, Milutin, Grujic, Nikola, van Renssen, André, Seybold, Martin P.
Rok vydání:	2019
Předmět:	Computer Science - Computational Geometry
Druh dokumentu:	Working Paper
Popis:	We study how to dynamize the Trapezoidal Search Tree - 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. Moreover, the dynamization carries over to the Trapezoidal Search DAG, offering a linear sized data structure with logarithmic point location costs as a by-product. On a set $S$ of non-crossing segments, each update performs expected ${\mathcal O}(\log^2|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. Comment: Dynamization, Trapezoidal Search Tree, Trapezoidal Search DAG, Backward Analysis, Point Location, Planar Subdivision, Treap
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1912.03389 Zobrazit plný text záznamu View this record from Arxiv