Worst-case optimal insertion and deletion methods for decomposable searching problems

DOI10.1016/0020-0190(81)90093-4MaRDI QIDQ1152223zbMATH OpenOpenAlexFDO

Authors Mark H. Overmars, J. Van Leeuwen

Publication date 1981

Published in Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

nearest neighbor searchingrange querying

Mathematics Subject Classification ID

Searching and sorting (68P10)

Cites work

• Decomposable searching problems
• Dynamization of order decomposable set problems
• scientific article; zbMATH DE number 3864511 (Why is no real title available?)
• scientific article; zbMATH DE number 3716801 (Why is no real title available?)
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• Optimal dynamization of decomposable searching problems
• Two general methods for dynamizing decomposable searching problems

Cited in

(29)

• Halfplanar range search in linear space and \(O(n^{0.695})\) query time
• A balanced search tree O(1) worst-case update time
• On the equivalence of some rectangle problems
• Divided \(k-d\) trees
• Applications of a new space-partitioning technique
• A dynamic fixed windowing problem
• Efficient splitting and merging algorithms for order decomposable problems.
• Improved bounds for finger search on a RAM
• Efficient independent set approximation in unit disk graphs
• Dynamic interpolation search revisited
• Computing rectangle enclosures
• Efficient dynamic range searching using data replication
• Time-optimal top-k document retrieval
• Resolving SINR Queries in a Dynamic Setting
• Towards an optimal method for dynamic planar point location
• Efficient splitting and merging algorithms for order decomposable problems
• Maintaining discrete probability distributions optimally
• AN EFFICIENT PARALLEL ALGORITHM FOR THE ASSIGNMENT PROBLEM ON THE PLANE∗
• Point location in dynamic planar subdivisions
• Dynamic graph coloring
• ISB-tree: A new indexing scheme with efficient expected behaviour
• Data Structures for Data-Intensive Applications: Tradeoffs and Design Guidelines
• Range (Rényi) entropy queries and partitioning
• Range entropy queries and partitioning
• Maintaining \(\mathrm{CMSO}_2\) properties on dynamic structures with bounded feedback vertex number
• Dynamic enumeration of similarity joins
• Dynamic layers of maxima with applications to dominating queries
• Efficient dynamic algorithms for some geometric intersection problems
• Two-tier relaxed heaps

This page was built for publication: Worst-case optimal insertion and deletion methods for decomposable searching problems

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