Back to Search
Start Over
TOWARDS AN OPTIMAL METHOD FOR DYNAMIC PLANAR POINT LOCATION.
- 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]
- Subjects :
- *DATA structures
*QUERYING (Computer science)
*LINEAR statistical models
Subjects
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