Optimal Expected-Time Algorithms for Closest Point Problems
From MaRDI portal
Publication:3883531
DOI10.1145/355921.355927zbMath0441.68077OpenAlexW2024766881MaRDI QIDQ3883531
Bruce W. Weide, Andrew Chi-Chih Yao, Jon Louis Bentley
Publication date: 1980
Published in: ACM Transactions on Mathematical Software (Search for Journal in Brave)
Full work available at URL: https://figshare.com/articles/journal_contribution/Optimal_expected-time_algorithms_for_closest-point_problems/6608108
computational geometryVoronoi diagramsminimum spanning treesoptimal algorithmsnearest neighbor searchingclosest point problems
Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10) Discrete mathematics in relation to computer science (68R99)
Related Items (50)
On the average complexity of 3D-Voronoi diagrams of random points on convex polytopes ⋮ Computing relative neighbourhood graphs in the plane ⋮ Expected time analysis for Delaunay point location ⋮ On the geometry of similarity search: dimensionality curse and concentration of measure ⋮ The region approach for computing relative neighbourhood graphs in the \(L_ p\) metric ⋮ Neighbours on a grid ⋮ A faster divide-and-conquer algorithm for constructing Delaunay triangulations ⋮ Dynamic closest pairs — A probabilistic approach ⋮ A sweepline algorithm for Voronoi diagrams ⋮ Some problems in computational geometry ⋮ The expected size of the sphere-of-influence graph ⋮ On the stabbing number of a random Delaunay triangulation ⋮ A linear expected-time algorithm for computing planar relative neighbourhood graphs ⋮ A symmetry based multiobjective clustering technique for automatic evolution of clusters ⋮ An O(n log n) algorithm for the all-nearest-neighbors problem ⋮ Accounting for boundary effects in nearest-neighbor searching ⋮ Self-organizing maps in population based metaheuristic to the dynamic vehicle routing problem ⋮ Stochastic Methods for Global Optimization ⋮ A note on linear expected time algorithms for finding convex hulls ⋮ An extension to \textsc{Voro++} for multithreaded computation of Voronoi cells ⋮ Greedy triangulation can be efficiently implemented in the average case ⋮ Stochastic global optimization methods part II: Multi level methods ⋮ The projector algorithm: a simple parallel algorithm for computing Voronoi diagrams and Delaunay graphs ⋮ Finding nearest neighbors with Voronoi tessellations ⋮ Order preserving extendible hashing and bucket tries ⋮ The extendible cell method for closest point problems ⋮ Self-organizing maps in evolutionary approach for the traveling salesman problem and vehicle routing problem with time windows ⋮ A practical approach to the 2D incremental nearest-point problem suitable for different point distributions ⋮ Randomized incremental construction of Delaunay and Voronoi diagrams ⋮ systolic array exploitation of a neural network inherent parallelism solving the nearest neighbor problem ⋮ Probably correct \(k\)-nearest neighbor search in high dimensions ⋮ Fast linear expected-time algorithms for computing maxima and convex hulls ⋮ A comparison of sequential Delaunay triangulation algorithms. ⋮ Approximate closest-point queries in high dimensions ⋮ GAPS: A clustering method using a new point symmetry-based distance measure ⋮ A new point symmetry based fuzzy genetic clustering technique for automatic evolution of clusters ⋮ Transport clustering and routing as a visual meshing process ⋮ Enhancing point symmetry-based distance for data clustering ⋮ Approximate model predictive control laws for constrained nonlinear discrete-time systems: analysis and offline design ⋮ An algorithm for geometric minimum spanning trees requiring nearly linear expected time ⋮ Clustering, classification and image segmentation on the grid ⋮ Analysis of N-trees ⋮ Expected-time complexity results for hierarchic clustering algorithms which use cluster centres ⋮ Monitoring correlative financial data streams by local pattern similarity ⋮ Defect location clustering schemes ⋮ Chromatic nearest neighbor searching: A query sensitive approach ⋮ On search by address computation ⋮ Higher-dimensional Voronoi diagrams in linear expected time ⋮ Approximate model predictive control laws for constrained nonlinear discrete-time systems: analysis and offline design ⋮ Evaluation of Range Searching Methods for Contact Searching in Mechanical Engineering
This page was built for publication: Optimal Expected-Time Algorithms for Closest Point Problems
