BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260530T210538Z
UID:Seminar-ACTO-498@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Nikhil Mande:MAILTO:Nikhil.Mande@liverpool
DTSTART:20191030T140000
DTEND:20191030T150000
SUMMARY:Algorithms, Complexity Theory and Optimisation Series
DESCRIPTION:Konstantinos Tsakalidis: An updating method for geometric data structures\n\nWe 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\nproblems. 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.\n\n[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)\n[SoCG'18] Timothy M. Chan, Konstantinos Tsakalidis: Dynamic Planar Orthogonal Point Location in Sublogarithmic Time. Symposium on Computational Geometry 2018: 25:1-25:15\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=498
LOCATION:
END:VEVENT
END:VCALENDAR