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 (only showing first 100 items - show all)
\( \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
This page was built for publication: A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
