ON ENUMERATING AND SELECTING DISTANCES

DOI10.1142/S0218195901000511zbMath1073.52506MaRDI QIDQ4682169

Timothy M. Chan

Publication date: 10 June 2005

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

zbMATH Keywords

randomized algorithms; range counting; closest pairs; distance selection; Distance enumeration

Mathematics Subject Classification ID

68W40: Analysis of algorithms

52B55: Computational aspects related to convexity

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

68W20: Randomized algorithms

Related Items

On approximate range counting and depth, A linear time algorithm for max-min length triangulation of a convex polygon, The Euclidean bottleneck Steiner path problem and other applications of \((\alpha ,\beta )\)-pair decomposition, Proximity problems on line segments spanned by points

Cites Work

• On counting pairs of intersecting segments and off-line triangle range searching
• The power of geometric duality
• An O(n log n) algorithm for the all-nearest-neighbors problem
• The complexity of selection and ranking in X+Y and matrices with sorted columns
• Randomized optimal algorithm for slope selection
• Reporting points in halfspaces
• Efficient partition trees
• Quasi-optimal upper bounds for simplex range searching and new zone theorems
• A note on Rabin's nearest-neighbor algorithm
• On range searching with semialgebraic sets
• Output-sensitive results on convex hulls, extreme points, and related problems
• A simple randomized sieve algorithm for the closest-pair problem
• Algorithms for proximity problems in higher dimensions
• Efficient construction of a bounded-degree spanner with low weight
• A simple algorithm for enumerating longest distances in the plane
• Selecting distances in the plane
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• ENUMERATING INTERDISTANCES IN SPACE
• SIMPLE ALGORITHMS FOR ENUMERATING INTERPOINT DISTANCES AND FINDING k NEAREST NEIGHBORS
• A Reliable Randomized Algorithm for the Closest-Pair Problem
• An Expander-Based Approach to Geometric Optimization
• Slowing down sorting networks to obtain faster sorting algorithms
• FINDING k FARTHEST PAIRS AND k CLOSEST/FARTHEST BICHROMATIC PAIRS FOR POINTS IN THE PLANE
• SEQUENTIAL AND PARALLEL ALGORITHMS FOR THE k CLOSEST PAIRS PROBLEM
• CUTTINGS AND APPLICATIONS
• A RANDOMIZED ALGORITHM FOR SLOPE SELECTION