A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
From MaRDI portal
Publication:4369857
DOI10.1145/200836.200853zbMATH Open0886.68078OpenAlexW2054011861WikidataQ30047665 ScholiaQ30047665MaRDI QIDQ4369857FDOQ4369857
Authors: Paul B. Callahan, S. R. Kosaraju 
Publication date: 2 February 1998
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/200836.200853
Recommendations
Cited In (only showing first 100 items - show all)
- Geometric spanners with small chromatic number
- Fast query structures in anisotropic media
- \( \delta \)-greedy \(t\)-spanner
- Sparse geometric graphs with small dilation
- On minimum- and maximum-weight minimum spanning trees with neighborhoods
- AN EFFECTIVE SETTING OF HIERARCHICAL CELL STRUCTURE FOR THE FAST MULTIPOLE BOUNDARY ELEMENT METHOD
- A cost optimal parallel algorithm for computing force field in \(N-\)body simulations on a CREW PRAM
- Routing on heavy-path WSPD-spanners
- On the dilation spectrum of paths, cycles, and trees
- Computing the greedy spanner in linear space
- New approximation algorithms for minimum cycle bases of graphs
- Fast algorithms for diameter-optimally augmenting paths
- (Weakly) self-approaching geometric graphs and spanners
- New constructions of SSPDs and their applications
- Polynomial-sized topological approximations using the permutahedron
- Chromatic nearest neighbor searching: A query sensitive approach
- Shortest paths in intersection graphs of unit disks
- Geometric spanners for weighted point sets
- Facility location and the geometric minimum-diameter spanning tree.
- Pruning spanners and constructing well-separated pair decompositions in the presence of memory hierarchies
- On the power of the semi-separated pair decomposition
- Spanners of Additively Weighted Point Sets
- Fitting a \(C^m\)-smooth function to data. II
- Title not available (Why is that?)
- Computing the greedy spanner in near-quadratic time
- Region-fault tolerant geometric spanners
- Metric spaces with expensive distances
- Distance-preserving approximations of polygonal paths
- Sobolev extension by linear operators
- Computing a \((1+\varepsilon)\)-approximate geometric minimum-diameter spanning tree
- An \(O(n)\) time hierarchical tree algorithm for computing force field in \(n\)-body simulations
- Computing the Expected Value and Variance of Geometric Measures
- Binary space partitions for axis-parallel line segments: Size-height tradeoffs.
- Approximate one-to-one point pattern matching
- Ramsey partitions and proximity data structures
- Provably Good Partitioning and Load Balancing Algorithms for Parallel Adaptive N-Body Simulation
- Approximate distance oracles for graphs with dense clusters
- Approximating the Fréchet distance for realistic curves in near linear time
- Nearest neighbors search using point location in balls with applications to approximate Voronoi decompositions
- Local geometric spanners
- On clustering induced Voronoi diagrams
- Construction of the nearest neighbor embracing graph of a point set
- The jet of an interpolant on a finite set
- Collision detection for deforming necklaces
- The \(C^m\) norm of a function with prescribed jets. II
- Constructing minimum-interference networks
- Fitting a \(C^m\)-smooth function to data. III.
- Approximating Minimization Diagrams and Generalized Proximity Search
- Space-Time Tradeoffs for Proximity Searching in Doubling Spaces
- Spanners of additively weighted point sets
- Energy-efficient paths in radio networks
- Computing the Greedy Spanner in Near-Quadratic Time
- Preprocessing imprecise points for Delaunay triangulation: simplified and extended
- An Optimal Dynamic Spanner for Doubling Metric Spaces
- On the Power of the Semi-Separated Pair Decomposition
- Approximate range searching
- Well-separated pair decomposition in linear time?
- Algorithms for graphs of bounded treewidth via orthogonal range searching
- Plastic card fraud detection using peer group analysis
- Deformable spanners and applications
- An optimal-time algorithm for shortest paths on a convex polytope in three dimensions
- I/O-efficient algorithms for computing planar geometric spanners
- The Weak Gap Property in Metric Spaces of Bounded Doubling Dimension
- Title not available (Why is that?)
- The Euclidean bottleneck Steiner path problem and other applications of \((\alpha ,\beta )\)-pair decomposition
- Sharp finiteness principles for Lipschitz selections
- Fast evaluation of potential and force field in particle systems using a fair-split tree spatial structure
- A simple and efficient method for accelerating construction of the gap-greedy spanner
- Influence-based Voronoi diagrams of clusters
- Dilation-Optimal Edge Deletion in Polygonal Cycles
- Approximating Distance Measures for the Skyline
- Average stretch factor: how low does it go?
- On some proximity problems of colored sets
- Title not available (Why is that?)
- A spanner for the day after
- A spanner for the day after
- Approximating the packedness of polygonal curves
- Edge sparsification for geometric tour problems
- Faster force-directed graph drawing with the well-separated pair decomposition
- Small hop-diameter sparse spanners for doubling metrics
- Bounded-degree plane geometric spanners in practice
- Kinetic \(k\)-semi-Yao graph and its applications
- Linear-size universal discretization of geometric center-based problems in fixed dimensions
- Kinetic reverse \(k\)-nearest neighbor problem
- Quickest path queries on transportation network
- Dilation-optimal edge deletion in polygonal cycles
- Routing on heavy path WSPD spanners
- Spanners under the Hausdorff and Fréchet distances
- Spanners of Complete k-Partite Geometric Graphs
- Fully dynamic geometric spanners
- Algorithms for nonnegative \(\mathrm{C}^2(\mathbb R^2)\) interpolation
- Dynamic smooth compressed quadtrees
- Sigma-local graphs
- On algorithmic complexity of imprecise spanners
- Efficient algorithms for approximate smooth selection
- A distributed kernel summation framework for general‐dimension machine learning
- An \(O(\log n)\) query time algorithm for reducing \(\varepsilon \)-NN to \((c,r)\)-NN
- Approximate $k$-Nearest Neighbor Graph on Moving Points
- \(C^2\) interpolation with range restriction
- Streaming Embeddings with Slack
This page was built for publication: A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4369857)
