An updating method for geometric data structures

30^th October 2019, 14:00
Konstantinos Tsakalidis
University of Liverpool

Abstract

We present the "micro-to-macro" updating method for dynamic data structures in the word-RAM model. Its application to dynamic planar orthogonal range reporting (report the input points within any given query rectangle) [JoCG'18] and point location (vertical ray shooting: report the lowest input horizontal line segment above any give query point) [SoCG'18] has achieved significantly sublogarithmic update time for these fundamental geometric
problems. These advancements have been used as subroutines towards improving more dynamic problems in computational geometry and stringology. In this talk we will present the method in its general form and will discuss its geometric variations in terms of a "range tree" and a "segment tree" formulation.

[JoCG'18] Timothy M. Chan, Konstantinos Tsakalidis: Dynamic orthogonal range searching on the RAM, revisited. Journal of Computational Geometry 2018: 9(2): 45-66 (Special Issue of Selected Papers from SoCG 2017)
[SoCG'18] Timothy M. Chan, Konstantinos Tsakalidis: Dynamic Planar Orthogonal Point Location in Sublogarithmic Time. Symposium on Computational Geometry 2018: 25:1-25:15