{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:46:23Z","timestamp":1725558383754},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540405450"},{"type":"electronic","value":"9783540450788"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-45078-8_39","type":"book-chapter","created":{"date-parts":[[2010,6,22]],"date-time":"2010-06-22T17:23:52Z","timestamp":1277227432000},"page":"451-461","source":"Crossref","is-referenced-by-count":4,"title":["Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries"],"prefix":"10.1007","author":[{"given":"David","family":"Bremner","sequence":"first","affiliation":[]},{"given":"Erik","family":"Demaine","sequence":"additional","affiliation":[]},{"given":"Jeff","family":"Erickson","sequence":"additional","affiliation":[]},{"given":"John","family":"Iacono","sequence":"additional","affiliation":[]},{"given":"Stefan","family":"Langerman","sequence":"additional","affiliation":[]},{"given":"Pat","family":"Morin","sequence":"additional","affiliation":[]},{"given":"Godfried","family":"Toussaint","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"39_CR1","doi-asserted-by":"crossref","unstructured":"Ben-Or, M.: Lower bounds for algebraic computation trees (preliminary report). In: Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, pp. 80\u201386 (1983)","DOI":"10.1145\/800061.808735"},{"issue":"1","key":"39_CR2","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1006\/jagm.1997.0869","volume":"25","author":"B.K. Bhattacharya","year":"1997","unstructured":"Bhattacharya, B.K., Sen, S.: On a simple, practical, optimal, output-sensitive randomized planar convex hull algorithm. Journal of Algorithms\u00a025(1), 177\u2013193 (1997)","journal-title":"Journal of Algorithms"},{"key":"39_CR3","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1016\/S0022-0000(73)80033-9","volume":"7","author":"M. Blum","year":"1973","unstructured":"Blum, M., Floyd, R.W., Pratt, V., Rivest, R.L., Tarjan, R.E.: Time bounds for selection. Journal of Computing and Systems Science\u00a07, 448\u2013461 (1973)","journal-title":"Journal of Computing and Systems Science"},{"key":"39_CR4","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1007\/BF02712873","volume":"16","author":"T.M. Chan","year":"1996","unstructured":"Chan, T.M.: Optimal output-sensitive convex hull algorithms in two and three dimensions. Discrete & Computational Geometry\u00a016, 361\u2013368 (1996)","journal-title":"Discrete & Computational Geometry"},{"key":"39_CR5","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/PL00009327","volume":"18","author":"T.M. Chan","year":"1997","unstructured":"Chan, T.M., Snoeyink, J., Yap, C.K.: Primal dividing and dual pruning: Output-sensitive construction of four-dimensional polytopes and three-dimensional Voronoi diagrams. Discrete & Computational Geometry\u00a018, 433\u2013454 (1997)","journal-title":"Discrete & Computational Geometry"},{"key":"39_CR6","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1109\/TIT.1967.1053964","volume":"13","author":"T.M. Cover","year":"1967","unstructured":"Cover, T.M., Hart, P.E.: Nearest neighbour pattern classification. IEEE Transactions on Information Theory\u00a013, 21\u201327 (1967)","journal-title":"IEEE Transactions on Information Theory"},{"key":"39_CR7","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/0031-3203(78)90047-X","volume":"10","author":"B. Dasarathy","year":"1978","unstructured":"Dasarathy, B., White, L.J.: A characterization of nearest-neighbour rule decision surfaces and a new approach to generate them. Pattern Recognition\u00a010, 41\u201346 (1978)","journal-title":"Pattern Recognition"},{"key":"39_CR8","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1109\/TPAMI.1981.4767052","volume":"3","author":"L. Devroye","year":"1981","unstructured":"Devroye, L.: On the inequality of Cover and Hart. IEEE Transactions on Pattern Analysis and Machine Intelligence\u00a03, 75\u201378 (1981)","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"39_CR9","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/0304-3975(82)90120-7","volume":"27","author":"D.P. Dobkin","year":"1983","unstructured":"Dobkin, D.P., Kirkpatrick, D.G.: Fast detection of poyhedral intersection. Theoretical Computer Science\u00a027, 241\u2013253 (1983)","journal-title":"Theoretical Computer Science"},{"key":"39_CR10","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1016\/0196-6774(85)90007-0","volume":"6","author":"D.P. Dobkin","year":"1985","unstructured":"Dobkin, D.P., Kirkpatrick, D.G.: A linear algorithm for determining the separation of convex polyhedra. Journal of Algorithms\u00a06, 381\u2013392 (1985)","journal-title":"Journal of Algorithms"},{"issue":"7","key":"39_CR11","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1145\/366622.366644","volume":"4","author":"C.A.R. Hoare","year":"1961","unstructured":"Hoare, C.A.R.: ACM Algorithm 64: Quicksort. Communications of the ACM\u00a04(7), 321 (1961)","journal-title":"Communications of the ACM"},{"issue":"1","key":"39_CR12","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1137\/0212002","volume":"12","author":"D.G. Kirkpatrick","year":"1983","unstructured":"Kirkpatrick, D.G.: Optimal search in planar subdivisions. SIAM Journal on Computing\u00a012(1), 28\u201335 (1983)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"39_CR13","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1137\/0215021","volume":"15","author":"D.G. Kirkpatrick","year":"1986","unstructured":"Kirkpatrick, D.G., Seidel, R.: The ultimate planar convex hull algorithm? SIAM Journal on Computing\u00a015(1), 287\u2013299 (1986)","journal-title":"SIAM Journal on Computing"},{"key":"39_CR14","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry","author":"F.P. Preparata","year":"1985","unstructured":"Preparata, F.P., Shamos, M.I.: Computational Geometry. Springer, Heidelberg (1985)"},{"key":"39_CR15","doi-asserted-by":"crossref","unstructured":"Shamos, M.I.: Geometric complexity. In: Proceedings of the 7th ACM Symposium on the Theory of Computing (STOC 1975), pp. 224\u2013253 (1975)","DOI":"10.1145\/800116.803772"},{"key":"39_CR16","doi-asserted-by":"publisher","first-page":"1348","DOI":"10.1214\/aos\/1176345206","volume":"8","author":"C. Stone","year":"1977","unstructured":"Stone, C.: Consistent nonparametric regression. Annals of Statistics\u00a08, 1348\u20131360 (1977)","journal-title":"Annals of Statistics"},{"key":"39_CR17","unstructured":"Toussaint, G.T.: Proximity graphs for instance-based learning. (2003) (manuscript)"},{"key":"39_CR18","unstructured":"Toussaint, G.T., Bhattacharya, B.K., Poulsen, R.S.: The application of Voronoi diagrams to non-parametric decision rules. In: Proceedings of Computer Science and Statistics: 16th Symposium of the Interface (1984)"},{"key":"39_CR19","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1007\/BF02523195","volume":"17","author":"R. Wenger","year":"1997","unstructured":"Wenger, R.: Randomized quick hull. Algorithmica\u00a017, 322\u2013329 (1997)","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-45078-8_39","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T05:48:37Z","timestamp":1559195317000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-45078-8_39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540405450","9783540450788"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-45078-8_39","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}