Untangled monotonic chains and adaptive range search

DOI10.1016/j.tcs.2011.01.037zbMath1221.68069MaRDI 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 geometry; implicit; range query; adaptive; data structure; monotonic chain; range search; untangling

Mathematics Subject Classification ID

68P10: Searching and sorting

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

68P05: Data structures

Related Items

Linear space adaptive data structures for planar range reporting, On compressing permutations and adaptive sorting, 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