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

• 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?)
• Decomposable searching problems
• Dynamization of order decomposable set problems
• Optimal dynamization of decomposable searching problems
• Two general methods for dynamizing decomposable searching problems

Cited in

(25)

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

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)