Search Results

Documents authored by Grujic, Nikola

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.18
A Simple Dynamization of Trapezoidal Point Location in Planar Subdivisions

Authors: Milutin Brankovic, Nikola Grujic, André van Renssen, and Martin P. Seybold

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
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.
Cite as

Milutin Brankovic, Nikola Grujic, André van Renssen, and Martin P. Seybold. A Simple Dynamization of Trapezoidal Point Location in Planar Subdivisions. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 18:1-18:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{brankovic_et_al:LIPIcs.ICALP.2020.18,
  author =	{Brankovic, Milutin and Grujic, Nikola and van Renssen, Andr\'{e} and Seybold, Martin P.},
  title =	{{A Simple Dynamization of Trapezoidal Point Location in Planar Subdivisions}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{18:1--18:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.18},
  URN =		{urn:nbn:de:0030-drops-124253},
  doi =		{10.4230/LIPIcs.ICALP.2020.18},
  annote =	{Keywords: Dynamization, Trapezoidal Search Tree, Trapezoidal Search DAG, Backward Analysis, Point Location, Planar Subdivision, Treap, Order-maintenance}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact