2026-07-29T10:45:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12425 2024-03-06T10:50:06Z ddc:004 open_access

A Simple Dynamization of Trapezoidal Point Location in Planar Subdivisions Brankovic, Milutin Grujic, Nikola van Renssen, André Seybold, Martin P. Dynamization Trapezoidal Search Tree Trapezoidal Search DAG Backward Analysis Point Location Planar Subdivision Treap Order-maintenance 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Milutin Brankovic and Nikola Grujic and André van Renssen and Martin P. Seybold 2020 Is Part Of LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2020.18 urn:nbn:de:0030-drops-124253 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.18 eng https://creativecommons.org/licenses/by/3.0/legalcode