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.
Article PDF
Similar content being viewed by others
References
P. K. Agarwal and J. Matoušek. Ray shooting and parametric search. InProc. 24th ACM Symp. Theory Comput., pp. 517–526, 1992.
A. Aggarwal, H. Imai, N. Katoh, and S. Suri. Findingk points with minimum diameter and rela problems.J. Algorithms, 12: 38–56, 1991.
M. Ajtai, J. Komlós, and E. Szemerédi. Sorting inc logn parallel steps.Combinatorica 3: 1–19, 1983.
J. L. Bentley and J. B. Saxe. Decomposable searching problems, I: Static-to-dynamic transformation.J. Algorithms, 1:301–358, 1980.
B. Chazelle. An optimal convex hull algorithm and new results on cuttings. InProc. 32nd IEEE Symp. Found. Comput. Sci., pp. 29–38, 1991.
B. Chazelle and H. Edelsbrunner. An improved algorithm for constructingkth-order Voronoi diagrams.IEEE Trans. Comput., 36:1349–1354, 1987.
B. Chazelle, L. J. Guibas, and D. T. Lee. The power of geometric duality.BIT, 25:76–90, 1985.
B. M. Chazelle and D. T. Lee. On a circle placement problem.Computing, 36:1–16, 1986.
B. Chazelle, M. Sharir, and E. Welzl. Quasi-optimal upper bounds for simplex range searching and new zone theorems. InProc. 6th ACM Symp. Comput. Geom., pp. 23–33, 1990.
R. Cole. Slowing down sorting networks to obtain faster sorting algorithms.J. Assoc. Comput. Mach., 34:200–208, 1987.
H. P. Croft, K. J. Falconer, and R. K. Guy.Unsolved Problems in Geometry. Springer-Verlag, New York, 1990.
A. Datta, H.-P. Lenhof, C. Schwarz, and M. Smid. Static and dynamic algorithms fork-point clustering problems. InProc. 3rd Workshop Algorithms Data Struct., pp. 265–276. Lecture Notes in Computer Science, vol. 709. Springer-Verlag, New York, 1993.
M. T. Dickerson, R. L. Drysdale, and J. R. Sack. Simple algorithm for enumerating interpoint distances and findingk nearest neighbors.Internat. J. Comput. Geom. Appl., 2:221–239, 1993.
D. P. Dobkin, R. L. Drysdale, and L. J. Guibas. Finding smallest polygons. In F. P. Preparata, ed.,Computational Geometry, pp. 181–214. Advances in Computing Research, vol. 1. JAI Press, Greenwich, CT, 1983.
H. Edelsbrunner and L. J. Guibas. Topologically sweeping an arrangement.J. Comput. System. Sci., 38:165–194, 1989.
H. Edelsbrunner, J. O'Rourke, and R. Seidel. Constructing arrangements of lines and hyperplanes with applications.SIAM J. Comput., 15:341–363, 1986.
D. Eppstein. New algorithms for minimum areak-gons. InProc. 3rd ACM-SIAM Symp. Discrete Algorithms, pp. 83–88, 1992.
D. Eppstein. Persistence, offline algorithms, and space compaction. Technical Report 91-54, Dept. Information and Computer Science, University of California, Irvine, 1991.
D. Eppstein and J. Erickson. Iterated nearest neighbors and finding minimal polytopes. InProc. 4th ACM-SIAM Symp. Discrete Algorithms, pp. 64–73, 1993.
D. Eppstein, M. Overmars, G. Rote, and G. Woeginer. Finding minimum areak-gons.Discrete Comput. Geom., 7:45–58, 1992.
P. Erdős and G. Szekeres. A combinatorial problem in geometry.Compositio Math., 2:463–470, 1935.
G. N. Frederickson and D. B. Johnson. The complexity of selection and raking inX+Y and matrices with sorted rows and columns.J. Comput. System Sci., 24:197–208, 1982.
F. W. Fredman and D. E. Willard. Trans-dichotomous algorithms for minimum spanning trees and shortest paths. InProc. 31st IEEE Symp. Found Comput. Sci., pp. 719–725, 1990.
R. L. Graham, B. L. Rothschild, and J. H. Spencer.Ramsey Theory, 2nd edn. Wiley, New York 1990.
J. Hershberger and S. Suri. Finding tailored paritions. InProc. 5th ACM Symp. Comput. Geom., pp. 255–265, 1989.
J. D. Horton. Sets with no empty convex 7-gons.Canad. Math. Bull., 26:482–484, 1983.
H.-P. Lenhof and M. Smid. Enumerating thek closest pairs optimally. InProc. 33rd IEEE Symp. Found. Comput. Sci., pp. 380–386, 1992.
J. Matoušek. On vertical ray-shooting in arrangements.Comput. Geom. Theory. Appl., 2:279–285, 1993.
N. Megiddo. Applying parallel computation algorithms in the design of serial algorithms.J. Assoc. Comput. Mach., 30:852–865, 1983.
K. Mulmuley. Output sensitive construction of levels and Voronoi diagrams inRd of order 1 tok. InProc. 22nd ACM Symp. Theory Comput., pp. 322–330, 1990.
M. H. Overmars, B. Scholten, and I. Vincent. Sets without empty convex 6-gons.Bull. EATCS, 37:160, 1989.
M. H. Overmars and C.-K. Yap. New upper bounds in Klee's measure problem.SIAM J. Comput., 20:1034–1045, 1991.
M. Smid. Maintaining the minimal distance of a point set in polylogarithmic time.Discrete Comput. Geom., 7:415–431, 1992.
P. M. Vaidya. AnO(n logn) algorithm for the all-nearest-neighbors problem.Discrete Comput. Geom., 4:101–115, 1989.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Eppstein, D., Erickson, J. Iterated nearest neighbors and finding minimal polytopes. Discrete Comput Geom 11, 321–350 (1994). https://doi.org/10.1007/BF02574012
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02574012