Efficient data structures for range searching on a grid

DOI10.1016/0196-6774(88)90041-7MaRDI QIDQ3777465zbMATH OpenOpenAlexFDO

Authors Mark H. Overmars

Publication date 1988

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://dspace.library.uu.nl/handle/1874/16542

zbMATH Keywords

2-dimensional range searchingcomputer graphicsdata structuresdatabase designinteger grid

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Orthogonal range searching in linear and almost-linear space
• A data structure for multi-dimensional range reporting
• Orthogonal Range Searching in Linear and Almost-Linear Space
• Data Structures for Retrieval on Square Grids
• On the difficulty of range searching.

Cited in

(18)

• Scanline algorithms on a grid
• The range 1 query (R1Q) problem
• An algorithm for handling many relational calculus queries efficiently.
• Dynamic planar range skyline queries in log logarithmic expected time
• Compressing dictionary matching index via sparsification technique
• Dynamic 3-sided planar range queries with expected doubly-logarithmic time
• Computing a poset from its realizer
• Efficient range searching for categorical and plain data
• Space-efficient data-analysis queries on grids
• Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing
• Data Structures for Retrieval on Square Grids
• Space-efficient data-analysis queries on grids
• scientific article; zbMATH DE number 645770 (Why is no real title available?)
• Using persistent data structures for adding range restrictions to searching problems
• scientific article; zbMATH DE number 1947378 (Why is no real title available?)
• scientific article; zbMATH DE number 1830732 (Why is no real title available?)
• Linear space data structures for two types of range search
• Fast local searches and updates in bounded universes

This page was built for publication: Efficient data structures for range searching on a grid

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