Well-separated pair decomposition in linear time?
From MaRDI portal
Publication:963421
DOI10.1016/j.ipl.2008.02.008zbMath1186.68492OpenAlexW2094974501MaRDI 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
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
Related Items (9)
On Locality-Sensitive Orderings and Their Applications ⋮ Dynamic coresets ⋮ Klee's measure problem made oblivious ⋮ Preprocessing imprecise points for Delaunay triangulation: simplified and extended ⋮ REVERSE NEAREST NEIGHBOR QUERIES IN FIXED DIMENSION ⋮ Light Euclidean Spanners with Steiner Points ⋮ On Locality-Sensitive Orderings and Their Applications ⋮ Window queries for intersecting objects, maximal points and approximations using coresets ⋮ Low-light trees, and tight lower bounds for Euclidean spanners
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
This page was built for publication: Well-separated pair decomposition in linear time?
