Randomized Data Structures for the Dynamic Closest-Pair Problem

DOI10.1137/S0097539794277718MaRDI QIDQ4210083zbMATH OpenOpenAlexFDO

Authors Rajeev Raman, Mordecai J. Golin, Christian Schwarz, Michiel Smid

Publication date 20 September 1998

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539794277718

zbMATH Keywords

computational geometrydynamic data structuresproximityrandomization

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• scientific article; zbMATH DE number 437555
• A Reliable Randomized Algorithm for the Closest-Pair Problem
• scientific article; zbMATH DE number 1383812
• A Randomized Algorithm for Closest-Point Queries
• Kinetic and dynamic data structures for closest pair and all nearest neighbors
• Efficient randomized incremental algorithm for the closest pair problem using Leafary trees
• A simple randomized sieve algorithm for the closest-pair problem
• scientific article; zbMATH DE number 794264
• A simple randomized O(N N)-time closest-pair algorithm in doubling metrics

Cited in

(21)

• Deferred data structure for the nearest neighbor problem
• Dynamic rectangular point location, with an application to the closest pair problem
• An optimal algorithm for closest-pair maintenance
• A simple randomized sieve algorithm for the closest-pair problem
• scientific article; zbMATH DE number 437555 (Why is no real title available?)
• A Randomized Algorithm for Closest-Point Queries
• scientific article; zbMATH DE number 1303605 (Why is no real title available?)
• A Reliable Randomized Algorithm for the Closest-Pair Problem
• scientific article; zbMATH DE number 1372522 (Why is no real title available?)
• scientific article; zbMATH DE number 1383812 (Why is no real title available?)
• scientific article; zbMATH DE number 2119699 (Why is no real title available?)
• scientific article; zbMATH DE number 794264 (Why is no real title available?)
• scientific article; zbMATH DE number 910882 (Why is no real title available?)
• New Techniques for Exact and Approximate Dynamic Closest-Point Problems
• Kinetic and dynamic data structures for closest pair and all nearest neighbors
• Dynamic closest pairs — A probabilistic approach
• Kinetic data structures for all nearest neighbors and closest pair in the plane
• Fast hierarchical clustering and other applications of dynamic closest pairs
• Efficient regular data structures and algorithms for dilation, location, and proximity problems
• Efficient randomized incremental algorithm for the closest pair problem using Leafary trees
• A parallel batch-dynamic data structure for the closest pair problem

This page was built for publication: Randomized Data Structures for the Dynamic Closest-Pair Problem

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