{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T09:27:48Z","timestamp":1774690068348,"version":"3.50.1"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1994,3,1]],"date-time":"1994-03-01T00:00:00Z","timestamp":762480000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1994,3,1]],"date-time":"1994-03-01T00:00:00Z","timestamp":762480000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[1994,3]]},"DOI":"10.1007\/bf02574012","type":"journal-article","created":{"date-parts":[[2007,3,22]],"date-time":"2007-03-22T12:08:49Z","timestamp":1174565329000},"page":"321-350","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":85,"title":["Iterated nearest neighbors and finding minimal polytopes"],"prefix":"10.1007","volume":"11","author":[{"given":"David","family":"Eppstein","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeff","family":"Erickson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[1994,3,1]]},"reference":[{"key":"BF02574012_CR1","doi-asserted-by":"crossref","unstructured":"P. K. Agarwal and J. Matou\u0161ek. Ray shooting and parametric search. InProc. 24th ACM Symp. Theory Comput., pp. 517\u2013526, 1992.","DOI":"10.1145\/129712.129763"},{"key":"BF02574012_CR2","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1016\/0196-6774(91)90022-Q","volume":"12","author":"A. Aggarwal","year":"1991","unstructured":"A. Aggarwal, H. Imai, N. Katoh, and S. Suri. Findingk points with minimum diameter and rela problems.J. Algorithms, 12: 38\u201356, 1991.","journal-title":"J. Algorithms"},{"key":"BF02574012_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02579338","volume":"3","author":"M. Ajtai","year":"1983","unstructured":"M. Ajtai, J. Koml\u00f3s, and E. Szemer\u00e9di. Sorting inc logn parallel steps.Combinatorica 3: 1\u201319, 1983.","journal-title":"Combinatorica"},{"key":"BF02574012_CR4","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1016\/0196-6774(80)90015-2","volume":"1","author":"J. L. Bentley","year":"1980","unstructured":"J. L. Bentley and J. B. Saxe. Decomposable searching problems, I: Static-to-dynamic transformation.J. Algorithms, 1:301\u2013358, 1980.","journal-title":"J. Algorithms"},{"key":"BF02574012_CR5","doi-asserted-by":"crossref","unstructured":"B. Chazelle. An optimal convex hull algorithm and new results on cuttings. InProc. 32nd IEEE Symp. Found. Comput. Sci., pp. 29\u201338, 1991.","DOI":"10.1109\/SFCS.1991.185345"},{"key":"BF02574012_CR6","doi-asserted-by":"publisher","first-page":"1349","DOI":"10.1109\/TC.1987.5009474","volume":"36","author":"B. Chazelle","year":"1987","unstructured":"B. Chazelle and H. Edelsbrunner. An improved algorithm for constructingkth-order Voronoi diagrams.IEEE Trans. Comput., 36:1349\u20131354, 1987.","journal-title":"IEEE Trans. Comput."},{"key":"BF02574012_CR7","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1007\/BF01934990","volume":"25","author":"B. Chazelle","year":"1985","unstructured":"B. Chazelle, L. J. Guibas, and D. T. Lee. The power of geometric duality.BIT, 25:76\u201390, 1985.","journal-title":"BIT"},{"key":"BF02574012_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02238188","volume":"36","author":"B. M. Chazelle","year":"1986","unstructured":"B. M. Chazelle and D. T. Lee. On a circle placement problem.Computing, 36:1\u201316, 1986.","journal-title":"Computing"},{"key":"BF02574012_CR9","doi-asserted-by":"crossref","unstructured":"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\u201333, 1990.","DOI":"10.1145\/98524.98532"},{"key":"BF02574012_CR10","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1145\/7531.7537","volume":"34","author":"R. Cole","year":"1987","unstructured":"R. Cole. Slowing down sorting networks to obtain faster sorting algorithms.J. Assoc. Comput. Mach., 34:200\u2013208, 1987.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF02574012_CR11","volume-title":"Unsolved Problems in Geometry","author":"H. P. Croft","year":"1990","unstructured":"H. P. Croft, K. J. Falconer, and R. K. Guy.Unsolved Problems in Geometry. Springer-Verlag, New York, 1990."},{"key":"BF02574012_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/3-540-57155-8_254","volume-title":"Proc. 3rd Workshop Algorithms Data Struct.","author":"A. Datta","year":"1993","unstructured":"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\u2013276. Lecture Notes in Computer Science, vol. 709. Springer-Verlag, New York, 1993."},{"key":"BF02574012_CR13","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1142\/S0218195992000147","volume":"2","author":"M. T. Dickerson","year":"1993","unstructured":"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\u2013239, 1993.","journal-title":"Internat. J. Comput. Geom. Appl."},{"key":"BF02574012_CR14","series-title":"Advances in Computing Research","first-page":"181","volume-title":"Computational Geometry","author":"D. P. Dobkin","year":"1983","unstructured":"D. P. Dobkin, R. L. Drysdale, and L. J. Guibas. Finding smallest polygons. In F. P. Preparata, ed.,Computational Geometry, pp. 181\u2013214. Advances in Computing Research, vol. 1. JAI Press, Greenwich, CT, 1983."},{"key":"BF02574012_CR15","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0022-0000(89)90038-X","volume":"38","author":"H. Edelsbrunner","year":"1989","unstructured":"H. Edelsbrunner and L. J. Guibas. Topologically sweeping an arrangement.J. Comput. System. Sci., 38:165\u2013194, 1989.","journal-title":"J. Comput. System. Sci."},{"key":"BF02574012_CR16","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1137\/0215024","volume":"15","author":"H. Edelsbrunner","year":"1986","unstructured":"H. Edelsbrunner, J. O'Rourke, and R. Seidel. Constructing arrangements of lines and hyperplanes with applications.SIAM J. Comput., 15:341\u2013363, 1986.","journal-title":"SIAM J. Comput."},{"key":"BF02574012_CR17","unstructured":"D. Eppstein. New algorithms for minimum areak-gons. InProc. 3rd ACM-SIAM Symp. Discrete Algorithms, pp. 83\u201388, 1992."},{"key":"BF02574012_CR18","series-title":"Technical Report","volume-title":"Persistence, offline algorithms, and space compaction","author":"D. Eppstein","year":"1991","unstructured":"D. Eppstein. Persistence, offline algorithms, and space compaction. Technical Report 91-54, Dept. Information and Computer Science, University of California, Irvine, 1991."},{"key":"BF02574012_CR19","unstructured":"D. Eppstein and J. Erickson. Iterated nearest neighbors and finding minimal polytopes. InProc. 4th ACM-SIAM Symp. Discrete Algorithms, pp. 64\u201373, 1993."},{"key":"BF02574012_CR20","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/BF02187823","volume":"7","author":"D. Eppstein","year":"1992","unstructured":"D. Eppstein, M. Overmars, G. Rote, and G. Woeginer. Finding minimum areak-gons.Discrete Comput. Geom., 7:45\u201358, 1992.","journal-title":"Discrete Comput. Geom."},{"key":"BF02574012_CR21","first-page":"463","volume":"2","author":"P. Erd\u0151s","year":"1935","unstructured":"P. Erd\u0151s and G. Szekeres. A combinatorial problem in geometry.Compositio Math., 2:463\u2013470, 1935.","journal-title":"Compositio Math."},{"key":"BF02574012_CR22","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/0022-0000(82)90048-4","volume":"24","author":"G. N. Frederickson","year":"1982","unstructured":"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\u2013208, 1982.","journal-title":"J. Comput. System Sci."},{"key":"BF02574012_CR23","doi-asserted-by":"crossref","unstructured":"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\u2013725, 1990.","DOI":"10.1109\/FSCS.1990.89594"},{"key":"BF02574012_CR24","volume-title":"Ramsey Theory","author":"R. L. Graham","year":"1990","unstructured":"R. L. Graham, B. L. Rothschild, and J. H. Spencer.Ramsey Theory, 2nd edn. Wiley, New York 1990.","edition":"2nd edn"},{"key":"BF02574012_CR25","doi-asserted-by":"crossref","unstructured":"J. Hershberger and S. Suri. Finding tailored paritions. InProc. 5th ACM Symp. Comput. Geom., pp. 255\u2013265, 1989.","DOI":"10.1145\/73833.73862"},{"key":"BF02574012_CR26","doi-asserted-by":"publisher","first-page":"482","DOI":"10.4153\/CMB-1983-077-8","volume":"26","author":"J. D. Horton","year":"1983","unstructured":"J. D. Horton. Sets with no empty convex 7-gons.Canad. Math. Bull., 26:482\u2013484, 1983.","journal-title":"Canad. Math. Bull."},{"key":"BF02574012_CR27","doi-asserted-by":"crossref","unstructured":"H.-P. Lenhof and M. Smid. Enumerating thek closest pairs optimally. InProc. 33rd IEEE Symp. Found. Comput. Sci., pp. 380\u2013386, 1992.","DOI":"10.1109\/SFCS.1992.267752"},{"key":"BF02574012_CR28","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1016\/0925-7721(93)90024-Z","volume":"2","author":"J. Matou\u0161ek","year":"1993","unstructured":"J. Matou\u0161ek. On vertical ray-shooting in arrangements.Comput. Geom. Theory. Appl., 2:279\u2013285, 1993.","journal-title":"Comput. Geom. Theory. Appl."},{"key":"BF02574012_CR29","doi-asserted-by":"publisher","first-page":"852","DOI":"10.1145\/2157.322410","volume":"30","author":"N. Megiddo","year":"1983","unstructured":"N. Megiddo. Applying parallel computation algorithms in the design of serial algorithms.J. Assoc. Comput. Mach., 30:852\u2013865, 1983.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF02574012_CR30","doi-asserted-by":"crossref","unstructured":"K. Mulmuley. Output sensitive construction of levels and Voronoi diagrams inRd of order 1 tok. InProc. 22nd ACM Symp. Theory Comput., pp. 322\u2013330, 1990.","DOI":"10.1145\/100216.100259"},{"key":"BF02574012_CR31","first-page":"160","volume":"37","author":"M. H. Overmars","year":"1989","unstructured":"M. H. Overmars, B. Scholten, and I. Vincent. Sets without empty convex 6-gons.Bull. EATCS, 37:160, 1989.","journal-title":"Bull. EATCS"},{"key":"BF02574012_CR32","doi-asserted-by":"publisher","first-page":"1034","DOI":"10.1137\/0220065","volume":"20","author":"M. H. Overmars","year":"1991","unstructured":"M. H. Overmars and C.-K. Yap. New upper bounds in Klee's measure problem.SIAM J. Comput., 20:1034\u20131045, 1991.","journal-title":"SIAM J. Comput."},{"key":"BF02574012_CR33","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1007\/BF02187852","volume":"7","author":"M. Smid","year":"1992","unstructured":"M. Smid. Maintaining the minimal distance of a point set in polylogarithmic time.Discrete Comput. Geom., 7:415\u2013431, 1992.","journal-title":"Discrete Comput. Geom."},{"key":"BF02574012_CR34","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/BF02187718","volume":"4","author":"P. M. Vaidya","year":"1989","unstructured":"P. M. Vaidya. AnO(n logn) algorithm for the all-nearest-neighbors problem.Discrete Comput. Geom., 4:101\u2013115, 1989.","journal-title":"Discrete Comput. Geom."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02574012.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/BF02574012\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02574012","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02574012.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,15]],"date-time":"2025-01-15T04:36:56Z","timestamp":1736915816000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/BF02574012"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,3]]},"references-count":34,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1994,3]]}},"alternative-id":["BF02574012"],"URL":"https:\/\/doi.org\/10.1007\/bf02574012","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,3]]},"assertion":[{"value":"9 July 1992","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 July 1993","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 March 1994","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}