Towards an Optimal Method for Dynamic Planar Point Location

Timothy M. Chan, Yakov Nekrich

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

Abstract

We describe a fully dynamic linear-space data structure for point location in connected planar subdivisions, or more generally vertical ray shooting among non-intersecting line segments, that supports queries in O(logn(loglogn)2) time and updates in O(log n log log n) time. This is the first data structure that achieves close to logarithmic query and update time simultaneously, ignoring log log n factors. We further show how to reduce the query time to O(logn log log n) in the RAM model with randomization. Alternatively, the query time can be lowered to O(log n) if the update time is increased to O(log 1+∈n) for any constant ∈ > 0, or vice versa.

Original languageEnglish (US)
Title of host publicationProceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015
PublisherIEEE Computer Society
Pages390-409
Number of pages20
ISBN (Electronic)9781467381918
DOIs
StatePublished - Dec 11 2015
Externally publishedYes
Event56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015 - Berkeley, United States
Duration: Oct 17 2015Oct 20 2015

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2015-December
ISSN (Print)0272-5428

Other

Other56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015
CountryUnited States
CityBerkeley
Period10/17/1510/20/15

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Towards an Optimal Method for Dynamic Planar Point Location'. Together they form a unique fingerprint.

  • Cite this

    Chan, T. M., & Nekrich, Y. (2015). Towards an Optimal Method for Dynamic Planar Point Location. In Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015 (pp. 390-409). [7354405] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; Vol. 2015-December). IEEE Computer Society. https://doi.org/10.1109/FOCS.2015.31