Well-separated pair decomposition in linear time?

DOI10.1016/j.ipl.2008.02.008zbMath1186.68492MaRDI QIDQ963421

Timothy M. Chan

Publication date: 19 April 2010

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

Full work available at URL: https://doi.org/10.1016/j.ipl.2008.02.008

zbMATH Keywords

computational geometry; approximation algorithms; quadtrees

Mathematics Subject Classification ID

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

68W25: Approximation algorithms

Related Items

Preprocessing imprecise points for Delaunay triangulation: simplified and extended, Dynamic coresets, Low-light trees, and tight lower bounds for Euclidean spanners, REVERSE NEAREST NEIGHBOR QUERIES IN FIXED DIMENSION, On Locality-Sensitive Orderings and Their Applications

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fast geometric approximation techniques and geometric embedding problems
• Sorting in linear time?
• Trans-dichotomous algorithms for minimum spanning trees and shortest paths
• A sparse graph almost as good as the complete graph on points in \(k\) dimensions
• An efficient algorithm for determining the convex hull of a finite planar set
• An optimal algorithm for approximate nearest neighbor searching fixed dimensions
• Geometric Spanner Networks
• Minimum Spanning Trees in k-Dimensional Space
• A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
• A randomized linear-time algorithm to find minimum spanning trees
• Deterministic sorting in O(nloglogn) time and linear space