License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2020.18
URN: urn:nbn:de:0030-drops-124253
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12425/
Go to the corresponding LIPIcs Volume Portal

Brankovic, Milutin ; Grujic, Nikola ; van Renssen, André ; Seybold, Martin P.

A Simple Dynamization of Trapezoidal Point Location in Planar Subdivisions

pdf-format:
LIPIcs-ICALP-2020-18.pdf (0.9 MB)

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.

BibTeX - Entry

@InProceedings{brankovic_et_al:LIPIcs:2020:12425,
  author =	{Milutin Brankovic and Nikola Grujic and Andr{\'e} van Renssen and Martin P. Seybold},
  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 =	{Artur Czumaj and Anuj Dawar and Emanuela Merelli},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12425},
  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}
}

Keywords: Dynamization, Trapezoidal Search Tree, Trapezoidal Search DAG, Backward Analysis, Point Location, Planar Subdivision, Treap, Order-maintenance
Collection: 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Issue Date: 2020
Date of publication: 29.06.2020
Supplementary Material: https://github.com/milutinB/dynamic_trapezoidal_map_impl

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI