Untangled monotonic chains and adaptive range search

DOI10.1016/j.tcs.2011.01.037zbMath1221.68069OpenAlexW3146418440MaRDI QIDQ553358

Patrick K. Nicholson, Reza Dorrigiv, J. Ian Munro, Meng He, Diego Arroyuelo, Matthew Skala, Alejandro López-Ortiz, Alejandro Salinger, Francisco Claude, Stephane Durocher

Publication date: 27 July 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.01.037

zbMATH Keywords

computational geometryimplicitrange queryadaptivedata structuremonotonic chainrange searchuntangling

Mathematics Subject Classification ID

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

Related Items (3)

On compressing permutations and adaptive sorting ⋮ Linear space adaptive data structures for planar range reporting ⋮ Succinct and Implicit Data Structures for Computational Geometry

Cites Work

• Unnamed Item
• Unnamed Item
• Orthogonal range searching in linear and almost-linear space
• On minimum \(k\)-modal partitions of permutations
• Decomposing a set of points into chains, with applications to permutation and circle graphs
• Fractional cascading. I: A data structuring technique
• An \(\Omega\) (n log n) lower bound for decomposing a set of points into chains
• Partitioning a sequence into few monotone subsequences
• Implicit data structures for fast search and update
• Approximating minimum cocolorings.
• Untangled Monotonic Chains and Adaptive Range Search
• Multidimensional binary search trees used for associative searching
• The priority R-tree
• A Comparative Study of Efficient Algorithms for Partitioning a Sequence into Monotone Subsequences

This page was built for publication: Untangled monotonic chains and adaptive range search