Iterated nearest neighbors and finding minimal polytopes
- 1 March 1994
- journal article
- Published by Springer Science and Business Media LLC in Discrete & Computational Geometry
- Vol. 11 (3), 321-350
- https://doi.org/10.1007/bf02574012
Abstract
We introduce a new method for finding several types of optimalk-point sets, minimizing perimeter, diameter, circumradius, and related measures, by testing sets of theO(k) nearest neighbors to each point. We argue that this is better in a number of ways than previous algorithms, which were based on high-order Voronoi diagrams. Our technique allows us for the first time to maintain minimal sets efficiently as new points are inserted, to generalize our algorithms to higher dimensions, to find minimal convexk-vertex polygons and polytopes, and to improve many previous results. We achieve many of our results via a new algorithm for finding rectilinear nearest neighbors in the plane in timeO(n logn+kn). We also demonstrate a related technique for finding minimum areak-point sets in the plane, based on testing sets of nearest vertical neighbors to each line segment determined by a pair of points. A generalization of this technique also allows us to find minimum volume and boundary measure sets in arbitrary dimensions.Keywords
This publication has 26 references indexed in Scilit:
- On vertical ray shooting in arrangementsComputational Geometry, 1993
- New Upper Bounds in Klee’s Measure ProblemSIAM Journal on Computing, 1991
- Finding k points with minimum diameter and related problemsJournal of Algorithms, 1991
- Topologically sweeping an arrangementJournal of Computer and System Sciences, 1989
- Slowing down sorting networks to obtain faster sorting algorithmsJournal of the ACM, 1987
- The power of geometric dualityBIT Numerical Mathematics, 1985
- Sets with No Empty Convex 7-GonsCanadian Mathematical Bulletin, 1983
- Applying Parallel Computation Algorithms in the Design of Serial AlgorithmsJournal of the ACM, 1983
- The complexity of selection and ranking in X + Y and matrices with sorted columnsJournal of Computer and System Sciences, 1982
- Decomposable searching problems I. Static-to-dynamic transformationJournal of Algorithms, 1980