Well-separated pair decomposition in linear time?
From MaRDI portal
Publication:963421
DOI10.1016/j.ipl.2008.02.008zbMath1186.68492MaRDI QIDQ963421
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
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
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
