{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T16:30:58Z","timestamp":1770741058971,"version":"3.49.0"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030115081","type":"print"},{"value":"9783030115098","type":"electronic"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-11509-8_1","type":"book-chapter","created":{"date-parts":[[2019,1,18]],"date-time":"2019-01-18T14:54:48Z","timestamp":1547823288000},"page":"1-15","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["New Directions in Approximate Nearest-Neighbor Searching"],"prefix":"10.1007","author":[{"given":"David M.","family":"Mount","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,1,19]]},"reference":[{"key":"1_CR1","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1137\/1.9781611975482.23","volume-title":"Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Ahmed Abdelkader","year":"2019","unstructured":"Abdelkader, A., Arya, S., da Fonseca, G.D., Mount, D.M.: Approximate nearest neighbor searching with non-Euclidean and weighted distances. In: Proceedings of 30th Annual ACM-SIAM Symposium on Discrete Algorithms (2019)"},{"key":"1_CR2","unstructured":"Abdelkader, A., Mount, D.M.: Economical delone sets for approximating convex bodies. In: Proceedings of 16th Scandinavian Workshop Algorithm Theory, pp. 4:1\u20134:12 (2018)"},{"key":"1_CR3","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/BF01099647","volume":"7","author":"IP Androulakis","year":"1995","unstructured":"Androulakis, I.P., Maranas, C.D., Floudas, C.A.: $$\\alpha $$BB: a global optimization method for general constrained nonconvex problems. J. Glob. Optim. 7, 337\u2013363 (1995)","journal-title":"J. Glob. Optim."},{"key":"1_CR4","unstructured":"Arya, S., da Fonseca, G.D., Mount, D.M.: Near-optimal $$\\varepsilon $$-kernel construction and related problems. In: Proceedings of 33rd International Symposium on Computational Geometry, pp. 10:1\u201310:15 (2017). https:\/\/arxiv.org\/abs\/1604.01175"},{"key":"1_CR5","doi-asserted-by":"publisher","first-page":"849","DOI":"10.1007\/s00454-016-9856-5","volume":"58","author":"S Arya","year":"2017","unstructured":"Arya, S., da Fonseca, G.D., Mount, D.M.: On the combinatorial complexity of approximating polytopes. Discrete Comput. Geom. 58, 849\u2013870 (2017)","journal-title":"Discrete Comput. Geom."},{"key":"1_CR6","doi-asserted-by":"crossref","unstructured":"Arya, S., da Fonseca, G.D., Mount, D.M.: Optimal approximate polytope membership. In: Proceedings of 28th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 270\u2013288 (2017)","DOI":"10.1137\/1.9781611974782.18"},{"key":"1_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/16M1061096","volume":"47","author":"S Arya","year":"2018","unstructured":"Arya, S., da Fonseca, G.D., Mount, D.M.: Approximate polytope membership queries. SIAM J. Comput. 47, 1\u201351 (2018)","journal-title":"SIAM J. Comput."},{"key":"1_CR8","doi-asserted-by":"crossref","unstructured":"Arya, S., Malamatos, T.: Linear-size approximate Voronoi diagrams. In: Proceedings of 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 147\u2013155 (2002)","DOI":"10.1145\/509907.510011"},{"key":"1_CR9","doi-asserted-by":"crossref","unstructured":"Arya, S., Malamatos, T., Mount, D.M.: Space-efficient approximate Voronoi diagrams. In: Proceedings of the 34th Annual ACM Symposium on the Theory of Computing, pp. 721\u2013730 (2002)","DOI":"10.1145\/509907.510011"},{"key":"1_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1613676.1613677","volume":"57","author":"S Arya","year":"2009","unstructured":"Arya, S., Malamatos, T., Mount, D.M.: Space-time tradeoffs for approximate nearest neighbor searching. J. Assoc. Comput. Mach. 57, 1\u201354 (2009)","journal-title":"J. Assoc. Comput. Mach."},{"key":"1_CR11","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/S0925-7721(00)00022-5","volume":"17","author":"S Arya","year":"2000","unstructured":"Arya, S., Mount, D.M.: Approximate range searching. Comput. Geom. Theory Appl. 17, 135\u2013163 (2000)","journal-title":"Comput. Geom. Theory Appl."},{"issue":"6","key":"1_CR12","doi-asserted-by":"publisher","first-page":"891","DOI":"10.1145\/293347.293348","volume":"45","author":"S Arya","year":"1998","unstructured":"Arya, S., Mount, D.M., Netanyahu, N.S., Silverman, R., Wu, A.Y.: An optimal algorithm for approximate nearest neighbor searching fixed dimensions. J. Assoc. Comput. Mach. 45(6), 891\u2013923 (1998)","journal-title":"J. Assoc. Comput. Mach."},{"key":"1_CR13","first-page":"1","volume-title":"Flavors of Geometry","author":"K Ball","year":"1997","unstructured":"Ball, K.: An elementary introduction to modern convex geometry. In: Levy, S. (ed.) Flavors of Geometry, pp. 1\u201358. Cambridge University Press, Cambridge (1997). (MSRI Publications, vol. 31)"},{"key":"1_CR14","first-page":"21","volume":"65","author":"I B\u00e1r\u00e1ny","year":"2000","unstructured":"B\u00e1r\u00e1ny, I.: The technique of M-regions and cap-coverings: a survey. Rend. Circ. Mat. Palermo 65, 21\u201338 (2000)","journal-title":"Rend. Circ. Mat. Palermo"},{"key":"1_CR15","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational Geometry: Algorithms and Applications","author":"M de Berg","year":"2010","unstructured":"de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-540-77974-2","edition":"3"},{"key":"1_CR16","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF00937167","volume":"29","author":"DP Bertsekas","year":"1979","unstructured":"Bertsekas, D.P.: Convexification procedures and decomposition methods for nonconvex optimization problems. J. Optim. Theor. Appl. 29, 169\u2013197 (1979)","journal-title":"J. Optim. Theor. Appl."},{"key":"1_CR17","doi-asserted-by":"crossref","unstructured":"Bespamyatnikh, S.N.: Dynamic algorithms for approximate neighbor searching. In: Proceedings of Eighth Canadian Conference on Computational Geometry, pp. 252\u2013257 (1996)","DOI":"10.1515\/9780773591134-044"},{"key":"1_CR18","doi-asserted-by":"crossref","unstructured":"Beygelzimer, A., Kakade, S., Langford, J.: Cover trees for nearest neighbor. In: Proceedings of 23rd International Conference on Machine Learning, pp. 97\u2013104 (2006)","DOI":"10.1145\/1143844.1143857"},{"key":"1_CR19","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/BF02573971","volume":"10","author":"H Br\u00f6nnimann","year":"1993","unstructured":"Br\u00f6nnimann, H., Chazelle, B., Pach, J.: How hard is halfspace range searching. Discrete Comput. Geom. 10, 143\u2013155 (1993)","journal-title":"Discrete Comput. Geom."},{"key":"1_CR20","unstructured":"Chan, T.M.: Closest-point problems simplified on the RAM. In: Proceedings of 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 472\u2013473 (2002)"},{"key":"1_CR21","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1006\/jagm.1996.0060","volume":"21","author":"B Chazelle","year":"1996","unstructured":"Chazelle, B., Matou\u0161ek, J.: On linear-time deterministic algorithms for optimization problems in fixed dimension. J. Algorithms 21, 579\u2013597 (1996)","journal-title":"J. Algorithms"},{"issue":"4","key":"1_CR22","doi-asserted-by":"publisher","first-page":"830","DOI":"10.1137\/0217052","volume":"17","author":"KL Clarkson","year":"1988","unstructured":"Clarkson, K.L.: A randomized algorithm for closest-point queries. SIAM J. Comput. 17(4), 830\u2013847 (1988)","journal-title":"SIAM J. Comput."},{"key":"1_CR23","doi-asserted-by":"crossref","unstructured":"Clarkson, K.L.: Building triangulations using $$\\varepsilon $$-nets. In: Proceedings of 38th Annual ACM Symposium on Theory of Computing, pp. 326\u2013335 (2006)","DOI":"10.1145\/1132516.1132564"},{"key":"1_CR24","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1006\/jagm.2000.1135","volume":"38","author":"CA Duncan","year":"2001","unstructured":"Duncan, C.A., Goodrich, M.T., Kobourov, S.: Balanced aspect ratio trees: combining the advantages of k-d trees and octrees. J. Algorithms 38, 303\u2013333 (2001)","journal-title":"J. Algorithms"},{"key":"1_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1112\/S0025579300002655","volume":"17","author":"G Ewald","year":"1970","unstructured":"Ewald, G., Larman, D.G., Rogers, C.A.: The directions of the line segments and of the $$r$$-dimensional balls on the boundary of a convex body in Euclidean space. Mathematika 17, 1\u201320 (1970)","journal-title":"Mathematika"},{"key":"1_CR26","doi-asserted-by":"crossref","unstructured":"Har-Peled, S.: A replacement for Voronoi diagrams of near linear size. In: Proceedings of 42nd Annual IEEE Symposium on Foundations of Computer, pp. 94\u2013103 (2001)","DOI":"10.1109\/SFCS.2001.959884"},{"key":"1_CR27","doi-asserted-by":"publisher","first-page":"944","DOI":"10.1137\/140959067","volume":"44","author":"S Har-Peled","year":"2015","unstructured":"Har-Peled, S., Kumar, N.: Approximating minimization diagrams and generalized proximity search. SIAM J. Comput. 44, 944\u2013974 (2015)","journal-title":"SIAM J. Comput."},{"key":"1_CR28","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, 1148\u20131184 (2006)","journal-title":"SIAM J. Comput."},{"key":"1_CR29","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/BF02096204","volume":"46","author":"D Hilbert","year":"1895","unstructured":"Hilbert, D.: \u00dcber die gerade linie als k\u00fcrzeste verbindung zweier punkte. Math. Ann. 46, 91\u201396 (1895)","journal-title":"Math. Ann."},{"key":"1_CR30","unstructured":"Krauthgamer, R., Lee, J.R.: Navigating nets: simple algorithms for proximity search. In: Proceedings of 15th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 798\u2013807 (2004)"},{"key":"1_CR31","unstructured":"Vernicos, C., Walsh, C.: Flag-approximability of convex bodies and volume growth of Hilbert geometries (2016). https:\/\/hal.archives-ouvertes.fr\/hal-01423693, hAL Archive (hal-01423693i)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-11509-8_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T17:19:19Z","timestamp":1710263959000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-11509-8_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030115081","9783030115098"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-11509-8_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"19 January 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CALDAM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Conference on Algorithms and Discrete Applied Mathematics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Kharagpur","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"India","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14 February 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 February 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"caldam2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/cse.iitkgp.ac.in\/conf\/CALDAM\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"86","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"22","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"26% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"9","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}