Well-separated pair decomposition in linear time?
From MaRDI portal
Publication:963421
DOI10.1016/J.IPL.2008.02.008zbMATH Open1186.68492OpenAlexW2094974501MaRDI QIDQ963421FDOQ963421
Authors: 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
Recommendations
- scientific article; zbMATH DE number 437554
- STACS 2005
- A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
- Geometric minimum spanning trees via well-separated pair decompositions
- I/O-efficient well-separated pair decomposition and applications
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
Cites Work
- An optimal algorithm for approximate nearest neighbor searching fixed dimensions
- An efficient algorithm for determining the convex hull of a finite planar set
- Trans-dichotomous algorithms for minimum spanning trees and shortest paths
- Geometric Spanner Networks
- A sparse graph almost as good as the complete graph on points in \(k\) dimensions
- A randomized linear-time algorithm to find minimum spanning trees
- Title not available (Why is that?)
- Deterministic sorting in O(nloglogn) time and linear space
- Title not available (Why is that?)
- A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
- Sorting in linear time?
- Title not available (Why is that?)
- Title not available (Why is that?)
- Minimum Spanning Trees in k-Dimensional Space
- Fast geometric approximation techniques and geometric embedding problems
- Title not available (Why is that?)
Cited In (12)
- Well-Separated Pair Decomposition for the Unit-Disk Graph Metric and Its Applications
- Dynamic coresets
- Title not available (Why is that?)
- Low-light trees, and tight lower bounds for Euclidean spanners
- I/O-efficient well-separated pair decomposition and applications
- Window queries for intersecting objects, maximal points and approximations using coresets
- REVERSE NEAREST NEIGHBOR QUERIES IN FIXED DIMENSION
- On locality-sensitive orderings and their applications
- Preprocessing imprecise points for Delaunay triangulation: simplified and extended
- Light Euclidean Spanners with Steiner Points
- Klee's measure problem made oblivious
- On Locality-Sensitive Orderings and Their Applications
This page was built for publication: Well-separated pair decomposition in linear time?
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q963421)
