Dynamic Orthogonal Range Searching on the RAM, Revisited
- Submitting institution
-
The University of Liverpool
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 12147
- Type
- D - Journal article
- DOI
-
10.20382/jocg.v9i2a5
- Title of journal
- Journal of Computational Geometry
- Article number
- 2
- First page
- 45
- Volume
- 9
- Issue
- 2
- ISSN
- 1920-180X
- Open access status
- Technical exception
- Month of publication
- June
- Year of publication
- 2018
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
1
- Research group(s)
-
-
- Citation count
- -
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- A preliminary version of this paper appeared at SoCG'17 and was invited to the journal special issue for highlights from the conference. As stated in "Predecessor Search" (ACM Computing Surveys vol.53, num.5, 2020), this paper presents the state of the art for high-dimensional range searching. The data structures developed in the paper are used, for example, in "Repetition Detection in a Dynamic String" (ESA'19), "An Algorithmic Study of Fully Dynamic Independent Sets for Map Labeling" (ESA'20), "Fréchet Distance Under Translation" (SODA'19), and "Planar Reachability Under Single Vertex or Edge Failures" (SODA'21).
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -