{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:01:25Z","timestamp":1725494485807},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540676904"},{"type":"electronic","value":"9783540449850"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44985-x_31","type":"book-chapter","created":{"date-parts":[[2007,11,13]],"date-time":"2007-11-13T15:17:33Z","timestamp":1194967053000},"page":"353-366","source":"Crossref","is-referenced-by-count":4,"title":["Efficient Expected-Case Algorithms for Planar Point Location"],"prefix":"10.1007","author":[{"given":"Sunil","family":"Arya","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Siu-Wing","family":"Cheng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David M.","family":"Mount","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"H.","family":"Ramesh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,3,15]]},"reference":[{"key":"31_CR1","unstructured":"U. Adamy and R. Seidel. Planar point location close to the information-theoretic lower bound. In Proc. 9th ACM-SIAM Sympos. Discrete Algorithms, 1998."},{"key":"31_CR2","unstructured":"S. Arya and H. Y. Fu. Expected-case complexity of approximate nearest neighbor searching. In Proc. 11th ACM-SIAM Sympos. Discrete Algorithms, pages 379\u2013388, 2000. Extended version appears as HKUST Technical Report HKUST-TCSC-2000-03, URL: http:\/\/www.cs.ust.hk\/tcsc\/RR ."},{"key":"31_CR3","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1007\/3-540-57155-8_247","volume-title":"Proc. 3rd Workshop Algorithms Data Struct.","author":"M. Bern","year":"1993","unstructured":"M. Bern, D. Eppstein, and S.-H. Teng. Parallel construction of quadtrees and quality triangulations. In Proc. 3rd Workshop Algorithms Data Struct., volume 709 of Lecture Notes in Computer Science, pages 188\u2013199. Springer-Verlag, 1993."},{"key":"31_CR4","doi-asserted-by":"crossref","unstructured":"P. B. Callahan and S. R. Kosaraju. A decomposition of multi-dimensional point-sets with applications to k-nearest-neighbors and n-body potential fields. In Proc. 24th Ann. ACM Sympos. Theory Comput., pages 546\u2013556, 1992.","DOI":"10.1145\/129712.129766"},{"key":"31_CR5","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1007\/PL00009234","volume":"22","author":"L. Devroye","year":"1998","unstructured":"L. Devroye, E. P. M\u00fccke, and B. Zhu. A note on point location in Delaunay triangulations of random points. Algorithmica, 22:477\u2013482, 1998.","journal-title":"Algorithmica"},{"key":"31_CR6","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1137\/0205015","volume":"5","author":"D. P. Dobkin","year":"1976","unstructured":"D. P. Dobkin and R. J. Lipton. Multidimensional searching problems. SIAM J. Comput., 5:181\u2013186, 1976.","journal-title":"SIAM J. Comput."},{"issue":"2","key":"31_CR7","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1145\/357337.357338","volume":"3","author":"M. Edahiro","year":"1984","unstructured":"M. Edahiro, I. Kokubo, and T. Asano. A new point-location algorithm and its practical efficiency \u2014 Comparison with existing algorithms. ACM Trans. Graph,. 3(2):86\u2013109, 1984.","journal-title":"ACM Trans. Graph"},{"issue":"2","key":"31_CR8","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1137\/0215023","volume":"15","author":"H. Edelsbrunner","year":"1986","unstructured":"H. Edelsbrunner, L. J. Guibas, and J. Stolfi. Optimal point location in a monotone subdivision. SIAM J. Comput., 15(2):317\u2013340, 1986.","journal-title":"SIAM J. Comput."},{"key":"31_CR9","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0020-0190(90)90111-A","volume":"35","author":"K.Y. Fung","year":"1990","unstructured":"K.Y. Fung, T.M. Nicholl, R.E. Tarjan, and C.J. VanWyk. Simplified linear-time jordan sorting and polygon clipping. Inform. Process. Lett., 35:85\u201392, 1990.","journal-title":"Inform. Process. Lett."},{"key":"31_CR10","unstructured":"M. T. Goodrich, M. Orletsky, and K. Ramaiyer. Methods for achieving fast query times in point location data structures. In Proc. 8th ACM-SIAM Sympos. Discrete Algorithms, pages 757\u2013766, 1997."},{"key":"31_CR11","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1137\/0121057","volume":"21","author":"T. C. Hu","year":"1971","unstructured":"T. C. Hu and A. Tucker. Optimum computer search trees. SIAM J. of Applied Math., 21:514\u2013532, 1971.","journal-title":"SIAM J. of Applied Math."},{"issue":"1","key":"31_CR12","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1137\/0212002","volume":"12","author":"D. G. Kirkpatrick","year":"1983","unstructured":"D. G. Kirkpatrick. Optimal search in planar subdivisions. SIAM J. Comput., 12(1):28\u201335, 1983.","journal-title":"SIAM J. Comput."},{"key":"31_CR13","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1007\/BF00264289","volume":"1","author":"D. E. Knuth","year":"1971","unstructured":"D. E. Knuth. Optimum binary search trees. Acta Informatica, 1:14\u201325, 1971.","journal-title":"Acta Informatica"},{"key":"31_CR14","series-title":"The Art of Computer Programming.","volume-title":"Sorting and Searching","author":"D. E. Knuth","year":"1973","unstructured":"D. E. Knuth. Sorting and Searching, volume 3 of The Art of Computer Programming. Addison-Wesley, Reading, MA, 1973."},{"key":"31_CR15","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"R. J. Lipton","year":"1980","unstructured":"R. J. Lipton and R. E. Tarjan. Applications of a planar separator theorem. SIAM J. Comput., 9:615\u2013627, 1980.","journal-title":"SIAM J. Comput."},{"key":"31_CR16","unstructured":"S. Maneewongvatana and D. M. Mount. Analysis of approximate nearest neighbor searching with clustered point sets. In ALENEX, 1999."},{"key":"31_CR17","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/BF00264563","volume":"5","author":"K. Mehlhorn","year":"1975","unstructured":"K. Mehlhorn. Nearly optimal binary search trees. Acta Informatica, 5:287\u2013295, 1975.","journal-title":"Acta Informatica"},{"key":"31_CR18","unstructured":"D. M. Mount and S. Arya. ANN: A library for approximate nearest neighbor searching. 2nd Annual CGC Workshop on Computational Geometry, URL: http:\/\/www.cs.umd.edu\/mount\/ANN,1997 ."},{"key":"31_CR19","doi-asserted-by":"crossref","unstructured":"E. P. M\u00fccke, I. Saias, and B. Zhu. Fast randomized point location without preprocessing in two-and three-dimensional Delaunay triangulations. In Proc. 12th Annu. ACM Sympos. Comput. Geom., pages 274\u2013283, 1996.","DOI":"10.1145\/237218.237396"},{"issue":"3-4","key":"31_CR20","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/S0747-7171(08)80064-8","volume":"10","author":"K. Mulmuley","year":"1990","unstructured":"K. Mulmuley. A fast planar partition algorithm, I. J. Symbolic Comput., 10(3-4): 53\u2013280, 1990.","journal-title":"J. Symbolic Comput."},{"issue":"7","key":"31_CR21","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1145\/6138.6151","volume":"29","author":"N. Sarnak","year":"1986","unstructured":"N. Sarnak and R. E. Tarjan. Planar point location using persistent search trees. Commun. ACM, 29(7):669\u2013679, July 1986.","journal-title":"Commun. ACM"},{"key":"31_CR22","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/BF02187718","volume":"4","author":"P. M. Vaidya","year":"1989","unstructured":"P. M. Vaidya. An O(n log n) algorithm for the all-nearest-neighbors problem. Discrete Comput. Geom., 4:101\u2013115, 1989.","journal-title":"Discrete Comput. Geom."}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory - SWAT 2000"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44985-X_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,4]],"date-time":"2019-05-04T06:40:37Z","timestamp":1556952037000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44985-X_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540676904","9783540449850"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-44985-x_31","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}