A dynamic stabbing-max data structure with sub-logarithmic query time

DOI10.1007/978-3-642-25591-5_19MaRDI QIDQ3104611zbMATH OpenOpenAlexFDO

Authors Yakov Nekrich

Publication date 16 December 2011

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1109.3890

Mathematics Subject Classification ID

Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: In this paper we describe a dynamic data structure that answers one-dimensional stabbing-max queries in optimal $O(logn/loglogn)$ time. Our data structure uses linear space and supports insertions and deletions in $O(logn)$ and $O(logn/loglogn)$ amortized time respectively. We also describe a $O(n(logn/loglogn{)}^{d-1})$ space data structure that answers $d$-dimensional stabbing-max queries in $O((logn/loglogn{)}^d)$ time. Insertions and deletions are supported in $O((logn/loglogn{)}^{d}loglogn)$ and $O((logn/loglogn{)}^d)$ amortized time respectively.

Recommendations

• An optimal dynamic interval stabbing-MAX data structure?
• Dynamic Planar Range Maxima Queries
• Algorithms - ESA 2003
• An optimal dynamic data structure for stabbing-semigroup queries
• Space efficient dynamic stabbing with fast queries

Cited in

(8)

• Dynamic stabbing queries with sub-logarithmic local updates for overlapping intervals
• An optimal dynamic data structure for stabbing-semigroup queries
• An optimal dynamic interval stabbing-MAX data structure?
• Space efficient dynamic stabbing with fast queries
• Dynamic planar orthogonal point location in sublogarithmic time
• Algorithms - ESA 2003
• Random access in persistent strings and segment selection
• Computing the LCP array of a labeled graph

This page was built for publication: A dynamic stabbing-max data structure with sub-logarithmic query time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3104611)