{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,24]],"date-time":"2025-08-24T01:25:00Z","timestamp":1755998700602,"version":"3.37.3"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2016,7,8]],"date-time":"2016-07-08T00:00:00Z","timestamp":1467936000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2016,7,8]],"date-time":"2016-07-08T00:00:00Z","timestamp":1467936000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1421231, CCF-1217462","CCF-1217462"],"award-info":[{"award-number":["CCF-1421231, CCF-1217462","CCF-1217462"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1117259"],"award-info":[{"award-number":["CCF-1117259"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-08-1-1015"],"award-info":[{"award-number":["N00014-08-1-1015"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100005302","name":"University of Illinois at Urbana-Champaign","doi-asserted-by":"publisher","award":["Graduate College Dissertation Completion Fellowship"],"award-info":[{"award-number":["Graduate College Dissertation Completion Fellowship"]}],"id":[{"id":"10.13039\/100005302","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1421231, CCF-1217462"],"award-info":[{"award-number":["CCF-1421231, CCF-1217462"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1161495"],"award-info":[{"award-number":["CCF-1161495"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2016,9]]},"DOI":"10.1007\/s00454-016-9801-7","type":"journal-article","created":{"date-parts":[[2016,7,8]],"date-time":"2016-07-08T15:49:24Z","timestamp":1467992964000},"page":"357-376","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Space Exploration via Proximity Search"],"prefix":"10.1007","volume":"56","author":[{"given":"Sariel","family":"Har-Peled","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nirman","family":"Kumar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David M.","family":"Mount","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benjamin","family":"Raichel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,7,8]]},"reference":[{"key":"9801_CR1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898717617","volume-title":"Introduction to the Mathematics of Subdivision Surfaces","author":"L-E Andersson","year":"2010","unstructured":"Andersson, L.-E., Stewart, N.F.: Introduction to the Mathematics of Subdivision Surfaces. SIAM, Philadelphia (2010)"},{"key":"9801_CR2","doi-asserted-by":"crossref","unstructured":"Barman, S.: Approximating nash equilibria and dense bipartite subgraphs via an approximate version of Caratheodory\u2019s theorem. In: Proceedings of 47th Annual Symposium on the Theory of Computing (STOC), pp. 361\u2013369 (2015)","DOI":"10.1145\/2746539.2746566"},{"key":"9801_CR3","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-33099-2","volume-title":"Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics","author":"S Basu","year":"2006","unstructured":"Basu, S., Pollack, R., Roy, M.F.: Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics. Springer, Berlin (2006)"},{"key":"9801_CR4","doi-asserted-by":"publisher","first-page":"930","DOI":"10.1103\/PhysRevLett.56.930","volume":"56","author":"G Binnig","year":"1986","unstructured":"Binnig, G., Quate, C.F., Gerber, Ch.: Atomic force microscope. Phys. Rev. Lett. 56, 930\u2013933 (1986)","journal-title":"Phys. Rev. Lett."},{"key":"9801_CR5","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1145\/357306.357310","volume":"1","author":"JF Blinn","year":"1982","unstructured":"Blinn, J.F.: A generalization of algebraic surface drawing. ACM Trans. Graph. 1, 235\u2013256 (1982)","journal-title":"ACM Trans. Graph."},{"issue":"1","key":"9801_CR6","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1016\/j.comgeo.2006.05.008","volume":"37","author":"J-D Boissonnat","year":"2007","unstructured":"Boissonnat, J.-D., Guibas, L.J., Oudot, S.: Learning smooth shapes by probing. Comput. Geom. Theory Appl. 37(1), 38\u201358 (2007)","journal-title":"Comput. Geom. Theory Appl."},{"issue":"4","key":"9801_CR7","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1145\/1824777.1824783","volume":"6","author":"KL Clarkson","year":"2010","unstructured":"Clarkson, K.L.: Coresets, sparse greedy approximation, and the Frank\u2013Wolfe algorithm. ACM Trans. Algorithms 6(4), 63 (2010)","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"9801_CR8","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0196-6774(87)90025-3","volume":"8","author":"R Cole","year":"1987","unstructured":"Cole, R., Yap, C.K.: Shape from probing. J. Algorithms 8(1), 19\u201338 (1987)","journal-title":"J. Algorithms"},{"key":"9801_CR9","doi-asserted-by":"crossref","unstructured":"Feder, T., Greene, D. H.: Optimal algorithms for approximate clustering. In: Proceedings of 20th Annual ACM Aymposium on Theory of computing (STOC), pp. 434\u2013444 (1988)","DOI":"10.1145\/62212.62255"},{"key":"9801_CR10","unstructured":"Goel, A., Indyk, P., Varadarajan, K. R.: Reductions among high dimensional proximity problems. In: Proceedings of 12th ACM\u2013SIAM Symposium on Discrete Algorithms (SODA), pp. 769\u2013778, (2001)"},{"key":"9801_CR11","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0304-3975(85)90224-5","volume":"38","author":"T Gonzalez","year":"1985","unstructured":"Gonzalez, T.: Clustering to minimize the maximum intercluster distance. Theor. Comput. Sci. 38, 293\u2013306 (1985)","journal-title":"Theor. Comput. Sci."},{"key":"9801_CR12","volume-title":"Geometric Approximation Algorithms. Mathematical Surveys and Monographs","author":"S Har-Peled","year":"2011","unstructured":"Har-Peled, S.: Geometric Approximation Algorithms. Mathematical Surveys and Monographs, vol. 173. American Mathematical Society, Providence (2011)"},{"key":"9801_CR13","doi-asserted-by":"publisher","first-page":"321","DOI":"10.4086\/toc.2012.v008a014","volume":"8","author":"S Har-Peled","year":"2012","unstructured":"Har-Peled, S., Indyk, P., Motwani, R.: Approximate nearest neighbors: towards removing the curse of dimensionality. Theory Comput. 8, 321\u2013350 (2012). Special issue in honor of Rajeev Motwani","journal-title":"Theory Comput."},{"key":"9801_CR14","unstructured":"Har-Peled, S., Kumar, N., Mount, D., Raichel, B.: Space exploration via proximity search. CoRR, \n                    http:\/\/arxiv.org\/abs\/1412.1398\n                    \n                   (2014)"},{"issue":"5","key":"9801_CR15","doi-asserted-by":"publisher","first-page":"1148","DOI":"10.1137\/S0097539704446281","volume":"35","author":"S Har-Peled","year":"2006","unstructured":"Har-Peled, S., Mendel, M.: Fast construction of nets in low dimensional metrics, and their applications. SIAM J. Comput. 35(5), 1148\u20131184 (2006)","journal-title":"SIAM J. Comput."},{"key":"9801_CR16","first-page":"877","volume-title":"Handbook of Discrete and Computational Geometry, Chapter 39","author":"P Indyk","year":"2004","unstructured":"Indyk, P.: Nearest neighbors in high-dimensional spaces. In: Goodman, J.E., O\u2019Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, Chapter 39, 2nd edn, pp. 877\u2013892. CRC Press, Boca Raton (2004)","edition":"2"},{"issue":"1","key":"9801_CR17","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/s10479-014-1707-2","volume":"226","author":"B Kalantari","year":"2015","unstructured":"Kalantari, B.: A characterization theorem and an algorithm for a convex hull problem. Ann. Oper. Res. 226(1), 301\u2013349 (2015)","journal-title":"Ann. Oper. Res."},{"key":"9801_CR18","volume-title":"The Fractal Geometry of Nature","author":"BB Mandelbrot","year":"1983","unstructured":"Mandelbrot, B.B.: The Fractal Geometry of Nature. Macmillan, New York (1983)"},{"key":"9801_CR19","doi-asserted-by":"crossref","unstructured":"Matou\u0161ek, J., Seidel, R., Welzl, E.: How to net a lot with little: small $$\\varepsilon $$-nets for disks and halfspaces. In: Proceedings of 6th Annual ACM Symposium on Computational Geometry (SoCG), pp. 16\u201322 (1990)","DOI":"10.1145\/98524.98530"},{"key":"9801_CR20","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1016\/0377-2217(84)90155-3","volume":"18","author":"JM Mulvey","year":"1984","unstructured":"Mulvey, J.M., Beck, M.P.: Solving capacitated clustering problems. Eur. J. Oper. Res. 18, 339\u2013348 (1984)","journal-title":"Eur. J. Oper. Res."},{"key":"9801_CR21","first-page":"615","volume":"12","author":"ABJ Novikoff","year":"1962","unstructured":"Novikoff, A.B.J.: On convergence proofs on perceptrons. Proc. Symp. Math. Theo. Automata 12, 615\u2013622 (1962)","journal-title":"Proc. Symp. Math. Theo. Automata"},{"key":"9801_CR22","doi-asserted-by":"crossref","unstructured":"Panahi, F., Adler, A., van der Stappen, A. F., Goldberg, K.: An efficient proximity probing algorithm for metrology. In: Proceedings of IEEE International Conference on Automation Science and Engineering (CASE), pp. 342\u2013349 (2013)","DOI":"10.1109\/CoASE.2013.6653995"},{"key":"9801_CR23","unstructured":"Smelik, R. M., De Kraker, K. J., Groenewegen, S. A., Tutenel, T., Bidarra, R.: A survey of procedural methods for terrain modelling. In: Proceedings of the CASA. Workshop on 3D Advanced Media In Gaming and Simulation (2009)"},{"key":"9801_CR24","doi-asserted-by":"publisher","first-page":"599","DOI":"10.1007\/BF01553911","volume":"4","author":"SS Skiena","year":"1989","unstructured":"Skiena, S.S.: Problems in geometric probing. Algorithmica 4, 599\u2013605 (1989)","journal-title":"Algorithmica"},{"key":"9801_CR25","first-page":"481","volume-title":"Handbook of Discrete and Computational Geometry, Chapter 26","author":"SS Skiena","year":"1997","unstructured":"Skiena, S.S.: Geometric reconstruction problems. In: Goodman, J.E., O\u2019Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, Chapter 26, pp. 481\u2013490. CRC Press LLC, Boca Raton (1997)"},{"key":"9801_CR26","unstructured":"Wikipedia. Atomic force microscopy\u2014Wikipedia, The Free Encyclopedia (2014)"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-016-9801-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-016-9801-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-016-9801-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-016-9801-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,17]],"date-time":"2020-05-17T06:34:06Z","timestamp":1589697246000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-016-9801-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,7,8]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,9]]}},"alternative-id":["9801"],"URL":"https:\/\/doi.org\/10.1007\/s00454-016-9801-7","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2016,7,8]]},"assertion":[{"value":"13 July 2015","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 May 2016","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 June 2016","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 July 2016","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}