An optimal dynamic data structure for stabbing-semigroup queries

DOI10.1137/10078791XMaRDI QIDQ2884577zbMATH OpenFDO

Authors Lars Arge, Haim Kaplan, Eyal Molad, Ke Yi, Pankaj K. Agarwal, Robert E. Tarjan

Publication date 30 May 2012

Published in SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

dynamic data structuressemigroup queriesstabbing queries

Mathematics Subject Classification ID

Data structures (68P05) Database theory (68P15)

Recommendations

• An optimal dynamic interval stabbing-MAX data structure?
• Dynamic stabbing queries with sub-logarithmic local updates for overlapping intervals
• Interval Stabbing Problems in Small Integer Ranges
• Space efficient dynamic stabbing with fast queries
• A dynamic stabbing-max data structure with sub-logarithmic query time

Cited in

(12)

• Stabbing horizontal segments with vertical rays
• Intersection joins under updates
• An optimal dynamic interval stabbing-MAX data structure?
• A dynamic stabbing-max data structure with sub-logarithmic query time
• Dynamic stabbing queries with sub-logarithmic local updates for overlapping intervals
• An (Almost) Optimal Solution for Orthogonal Point Enclosure Query in ℝ³
• On the dynamic one-dimensional interval management problem in external memory
• Optimal External Memory Interval Management
• Random access in persistent strings and segment selection
• Space efficient dynamic stabbing with fast queries
• Dynamic planar orthogonal point location in sublogarithmic time
• Self-stabilizing overlays for high-dimensional monotonic searchability

This page was built for publication: An optimal dynamic data structure for stabbing-semigroup queries

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