Efficient splitting and merging algorithms for order decomposable problems.

DOI10.1006/inco.1999.2811zbMath1045.68556OpenAlexW1999644473MaRDI QIDQ1854311

Giuseppe F. Italiano, Roberto Grossi

Publication date: 14 January 2003

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/640c5b6bee885e7f6fde738f6211b47d92c9f0bc

zbMATH Keywords

Voronoi diagrams

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Computational aspects related to convexity (52B55) Data structures (68P05)

Related Items (2)

Cache-oblivious range reporting with optimal queries requires superlinear space ⋮ A general approach for cache-oblivious range reporting and approximate range counting

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Multidimensional divide-and-conquer
• The design of dynamic data structures
• A linear-time algorithm for computing the Voronoi diagram of a convex polygon
• On the dynamization of data structures
• General methods for adding range restrictions to decomposable searching problems
• A linear algorithm for finding the convex hull of a simple polygon
• Some principles for dynamizing decomposable searching problems
• Two general methods for dynamizing decomposable searching problems
• Worst-case optimal insertion and deletion methods for decomposable searching problems
• Optimal dynamization of decomposable searching problems
• Maintenance of configurations in the plane
• Dynamic multi-dimensional data structures based on quad- and k-d trees
• Divided \(k-d\) trees
• Decomposable searching problems
• Concatenable structures for decomposable problems
• Quad trees: A data structure for retrieval by composite keys
• On the computational power of pushdown automata
• Union-copy structures and dynamic segment trees
• A new approach to rectangle intersections part I
• Batched dynamic solutions to decomposable searching problems
• Adding range restriction capability to dynamic data structures
• Decomposable searching problems I. Static-to-dynamic transformation
• Dynamization of order decomposable set problems
• Lower bounds on the efficiency of transforming static data structures into dynamic structures
• Multidimensional binary search trees used for associative searching
• Maintenance of geometric extrema
• Efficient splitting and merging algorithms for order decomposable problems
• Binary Search Trees of Bounded Balance

This page was built for publication: Efficient splitting and merging algorithms for order decomposable problems.