Untangled monotonic chains and adaptive range search

DOI10.1016/J.TCS.2011.01.037MaRDI QIDQ553358zbMATH OpenOpenAlexFDO

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

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 geometrydata structureimplicitrange queryadaptivemonotonic chainrange searchuntangling

Mathematics Subject Classification ID

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

Recommendations

• Untangled monotonic chains and adaptive range search
• Orthogonal range searching in linear and almost-linear space
• Orthogonal Range Searching in Linear and Almost-Linear Space
• Adaptive and approximate orthogonal range counting
• Adaptive and approximate orthogonal range counting

Cites work

• scientific article; zbMATH DE number 3882232 (Why is no real title available?)
• scientific article; zbMATH DE number 1445373 (Why is no real title available?)
• A Comparative Study of Efficient Algorithms for Partitioning a Sequence into Monotone Subsequences
• An \(\Omega\) (n log n) lower bound for decomposing a set of points into chains
• Approximating minimum cocolorings.
• Decomposing a set of points into chains, with applications to permutation and circle graphs
• Fractional cascading. I: A data structuring technique
• Implicit data structures for fast search and update
• Multidimensional binary search trees used for associative searching
• On minimum \(k\)-modal partitions of permutations
• Orthogonal range searching in linear and almost-linear space
• Partitioning a sequence into few monotone subsequences
• The priority R-tree: a practically efficient and worst-case optimal R-tree
• Untangled monotonic chains and adaptive range search

Cited in

(4)

• Linear space adaptive data structures for planar range reporting
• On compressing permutations and adaptive sorting
• Untangled monotonic chains and adaptive range search
• Succinct and Implicit Data Structures for Computational Geometry

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

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