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.200853zbMath0886.68078OpenAlexW2054011861WikidataQ30047665 ScholiaQ30047665MaRDI QIDQ4369857
S. Rao Kosaraju, Paul B. Callahan
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
Related Items
Cyclically parallelized treecode for fast computations of electrostatic interactions on molecular surfaces, On algorithmic complexity of imprecise spanners, \(C^2\) interpolation with range restriction, Differentiate data by higher-order structures, Unnamed Item, Approximating the Packedness of Polygonal Curves, \( \delta \)-greedy \(t\)-spanner, Linear-size universal discretization of geometric center-based problems in fixed dimensions, Computing a \((1+\varepsilon)\)-approximate geometric minimum-diameter spanning tree, Kinetic \(k\)-semi-Yao graph and its applications, Routing on heavy-path WSPD-spanners, Algorithms for graphs of bounded treewidth via orthogonal range searching, On the dilation spectrum of paths, cycles, and trees, Fast Algorithms for Diameter-Optimally Augmenting Paths, (Weakly) self-approaching geometric graphs and spanners, Sharp finiteness principles for Lipschitz selections, On the Power of the Semi-Separated Pair Decomposition, Streaming Embeddings with Slack, DILATION-OPTIMAL EDGE DELETION IN POLYGONAL CYCLES, Computing the Expected Value and Variance of Geometric Measures, Fitting a \(C^m\)-smooth function to data. III., Distance-preserving approximations of polygonal paths, Collision detection for deforming necklaces, An \(O(n)\) time hierarchical tree algorithm for computing force field in \(n\)-body simulations, Approximate distance oracles for graphs with dense clusters, Spanners for Directed Transmission Graphs, Kinetic Reverse k-Nearest Neighbor Problem, Fast query structures in anisotropic media, A graph-based N-body approximation with application to stochastic neighbor embedding, Computing the greedy spanner in linear space, On Clustering Induced Voronoi Diagrams, New constructions of SSPDs and their applications, Spanners of Additively Weighted Point Sets, Computing the Greedy Spanner in Near-Quadratic Time, Low-interference networks in metric spaces of bounded doubling dimension, Approximate $k$-Nearest Neighbor Graph on Moving Points, New approximation algorithms for minimum cycle bases of graphs, Robust proximity search for balls using sublinear space, Geometric spanners for weighted point sets, On the power of the semi-separated pair decomposition, Spanners of additively weighted point sets, Energy-efficient paths in radio networks, Approximate range closest-pair queries, Approximating the Fréchet distance for realistic curves in near linear time, Spanners for geodesic graphs and visibility graphs, Preprocessing imprecise points for Delaunay triangulation: simplified and extended, Approximate one-to-one point pattern matching, The Euclidean bottleneck Steiner path problem and other applications of \((\alpha ,\beta )\)-pair decomposition, Computing the greedy spanner in near-quadratic time, Facility location and the geometric minimum-diameter spanning tree., Space-Time Tradeoffs for Proximity Searching in Doubling Spaces, An Optimal Dynamic Spanner for Doubling Metric Spaces, Constructing minimum-interference networks, Sparse geometric graphs with small dilation, I/O-efficient algorithms for computing planar geometric spanners, A spanner for the day after, Dilation-Optimal Edge Deletion in Polygonal Cycles, Fast evaluation of potential and force field in particle systems using a fair-split tree spatial structure, Faster force-directed graph drawing with the well-separated pair decomposition, Polynomial-sized topological approximations using the permutahedron, Routing in unit disk graphs, Influence-based Voronoi diagrams of clusters, Plastic card fraud detection using peer group analysis, Geometric spanners with small chromatic number, Quickest path queries on transportation network, Small hop-diameter sparse spanners for doubling metrics, Construction of the nearest neighbor embracing graph of a point set, Provably Good Partitioning and Load Balancing Algorithms for Parallel Adaptive N-Body Simulation, Well-separated pair decomposition in linear time?, The jet of an interpolant on a finite set, An optimal-time algorithm for shortest paths on a convex polytope in three dimensions, A cost optimal parallel algorithm for computing force field in \(N-\)body simulations on a CREW PRAM, Sigma-local graphs, Unnamed Item, Pruning spanners and constructing well-separated pair decompositions in the presence of memory hierarchies, Deformable spanners and applications, Nearest neighbors search using point location in balls with applications to approximate Voronoi decompositions, An \(O(\log n)\) query time algorithm for reducing \(\varepsilon \)-NN to \((c,r)\)-NN, Algorithms for nonnegative \(\mathrm{C}^2(\mathbb R^2)\) interpolation, Ramsey partitions and proximity data structures, Spanners of Complete k-Partite Geometric Graphs, Unnamed Item, AN EFFECTIVE SETTING OF HIERARCHICAL CELL STRUCTURE FOR THE FAST MULTIPOLE BOUNDARY ELEMENT METHOD, Unnamed Item, Efficient algorithms for approximate smooth selection, A distributed kernel summation framework for general‐dimension machine learning, Region-fault tolerant geometric spanners, Fitting a \(C^m\)-smooth function to data. II, The \(C^m\) norm of a function with prescribed jets. II, Fully dynamic geometric spanners, Approximating Distance Measures for the Skyline, The Weak Gap Property in Metric Spaces of Bounded Doubling Dimension, Local geometric spanners, Dynamic smooth compressed quadtrees, Approximating Minimization Diagrams and Generalized Proximity Search, Small candidate set for translational pattern search, Approximating the packedness of polygonal curves, Average stretch factor: how low does it go?, Binary space partitions for axis-parallel line segments: Size-height tradeoffs., Metric Spaces with Expensive Distances, Sobolev extension by linear operators, Chromatic nearest neighbor searching: A query sensitive approach, Approximate range searching, Shortest paths in intersection graphs of unit disks, On minimum- and maximum-weight minimum spanning trees with neighborhoods, On Some Proximity Problems of Colored Sets
