Back to Search Start Over

TOWARDS AN OPTIMAL METHOD FOR DYNAMIC PLANAR POINT LOCATION.

Authors :
CHAN, TIMOTHY M.
NEKRICH, YAKOV
Source :
SIAM Journal on Computing. 2018, Vol. 47 Issue 6, p2337-2361. 25p.
Publication Year :
2018

Abstract

We describe a fully dynamic linear-space data structure for point location in connected planar subdivisions, or more generally vertical ray shooting among nonintersecting line segments, that supports queries in O(log n(log log n)²) 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(log n 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(log1+ε n) for any constant ε > 0, or vice versa. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
00975397
Volume :
47
Issue :
6
Database :
Academic Search Index
Journal :
SIAM Journal on Computing
Publication Type :
Academic Journal
Accession number :
133715666
Full Text :
https://doi.org/10.1137/16M1066506