Dynamic planar orthogonal point location in sublogarithmic time

Timothy M. Chan, Konstantinos Tsakalidis

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We study a longstanding problem in computational geometry: dynamic 2-d orthogonal point location, i.e., vertical ray shooting among n horizontal line segments. We present a data structure achieving O(log n/log log n) optimal expected query time and O(log1/2+ϵ n) update time (amortized) in the word-RAM model for any constant ϵ > 0, under the assumption that the x-coordinates are integers bounded polynomially in n. This substantially improves previous results of Giyora and Kaplan [SODA 2007] and Blelloch [SODA 2008] with O (log n) query and update time, and of Nekrich (2010) with O(log n/log log n) query time and O (log1+ϵ n) update time. Our result matches the best known upper bound for simpler problems such as dynamic 2-d dominance range searching. We also obtain similar bounds for orthogonal line segment intersection reporting queries, vertical ray stabbing, and vertical stabbing-max, improving previous bounds, respectively, of Blelloch [SODA 2008] and Mortensen [SODA 2003], of Tao (2014), and of Agarwal, Arge, and Yi [SODA 2005] and Nekrich [ISAAC 2011].

Original languageEnglish (US)
Title of host publication34th International Symposium on Computational Geometry, SoCG 2018
EditorsCsaba D. Toth, Bettina Speckmann
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages251-2515
Number of pages2265
ISBN (Electronic)9783959770668
DOIs
StatePublished - Jun 1 2018
Event34th International Symposium on Computational Geometry, SoCG 2018 - Budapest, Hungary
Duration: Jun 11 2018Jun 14 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume99
ISSN (Print)1868-8969

Other

Other34th International Symposium on Computational Geometry, SoCG 2018
CountryHungary
CityBudapest
Period6/11/186/14/18

Keywords

  • Dynamic data structures
  • Point location
  • Word RAM

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Dynamic planar orthogonal point location in sublogarithmic time'. Together they form a unique fingerprint.

Cite this