On Cartesian Trees and Range Minimum Queries

2009/01/01 by Erik D. Demaine, Gad M. Landau, Oren Weimann · 37 citations
Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Binary tree #Bottleneck #Cartesian coordinate system #Cartesian product #Combinatorics #Computer science #Data Management and Algorithms #Discrete mathematics #Geometry #Graph Theory and Algorithms #Information retrieval #Interval tree #Mathematics #Range (aeronautics) #Range query (database) #Range tree #Sargable #Theoretical computer science #Tree (set theory) #Tree structure #Web search query

paper · open access · doi:10.1007/978-3-642-02927-1_29

published in Lecture Notes in Computer Science, 341-353 (Springer Berlin Heidelberg)

crossref issued 2009/01/01 · crossref published 2009/01/01 · crossref published-print 2009/01/01 · openalex publication_date 2009/01/01 · crossref created 2009/07/04 · crossref deposited 2025/02/10 · openalex created_date 2025/10/10 · crossref indexed 2026/03/02 · openalex updated_date 2026/08/04

Citations

• Lowest common ancestors in trees and directed acyclic graphs
• Scaling and related techniques for geometry problems
• Fast Algorithms for Finding Nearest Common Ancestors
• A data structure for dynamic trees
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• Recursive Star-Tree Parallel Data Structure
• Cache-oblivious algorithms
• An inverse-Ackermann style lower bound for the online minimum spanning tree verification problem
• A randomized linear-time algorithm to find minimum spanning trees
• Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE

Cited by

• Cartesian tree [wikipedia]