{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T20:31:25Z","timestamp":1725568285687},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540671817"},{"type":"electronic","value":"9783540465157"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/978-3-540-46515-7_21","type":"book-chapter","created":{"date-parts":[[2010,10,20]],"date-time":"2010-10-20T09:35:28Z","timestamp":1287567328000},"page":"250-257","source":"Crossref","is-referenced-by-count":2,"title":["Grouping and Querying: A Paradigm to Get Output-Sensitive Algorithms"],"prefix":"10.1007","author":[{"given":"Frank","family":"Nielsen","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"21_CR1","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1016\/0020-0190(72)90045-2","volume":"1","author":"R.L. Graham","year":"1972","unstructured":"Graham, R.L.: An efficient algorithm for determining the convex hull of a finite planar set. Inform. Process. Lett.\u00a01, 132\u2013133 (1972)","journal-title":"Inform. Process. Lett."},{"key":"21_CR2","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 J. Comput.\u00a015, 287\u2013299 (1986)","journal-title":"SIAM J. Comput."},{"key":"21_CR3","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. J. Algorithms\u00a025, 177\u2013193 (1997)","journal-title":"J. Algorithms"},{"key":"21_CR4","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1137\/0220016","volume":"20","author":"H. Edelsbrunner","year":"1991","unstructured":"Edelsbrunner, H., Shi, W.: An 0(n log2 h) time algorithm for the three-dimensional convex hull problem. SIAM J. Comput.\u00a020, 259\u2013277 (1991)","journal-title":"SIAM J. Comput."},{"key":"21_CR5","doi-asserted-by":"crossref","unstructured":"Ben-Or, M.: Lower bounds for algebraic computation trees. In: Proc. 15th Annu. ACM Sympos. Theory Comput., pp. 80\u201386 (1983)","DOI":"10.1145\/800061.808735"},{"key":"21_CR6","unstructured":"Nielsen, F.: Algorithmes Geometriques Adaptatifs - Adaptive Computational Geometry. Ph.D. thesis, Nice Univ. (France) (1996) isbn - 2 - 7261 - 1017 - 7"},{"key":"21_CR7","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 Comput. Geom.\u00a016, 361\u2013368 (1996)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"21_CR8","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1142\/S0218195998000047","volume":"8","author":"F. Nielsen","year":"1998","unstructured":"Nielsen, F., Yvinec, M.: An output-sensitive convex hull algorithm for planar objects. Internat. J. Comput. Geom. Appl.\u00a08(1), 39\u201366 (1998)","journal-title":"Internat. J. Comput. Geom. Appl."},{"key":"21_CR9","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/0020-0190(96)00116-0","volume":"59","author":"F. Nielsen","year":"1996","unstructured":"Nielsen, F.: Output-sensitive peeling of convex and maximal layers. Inform. Process. Lett.\u00a059, 255\u2013259 (1996)","journal-title":"Inform. Process. Lett."},{"key":"21_CR10","unstructured":"Nielsen, F.: Constrained geometric pattern matching and its applications. In: Proc. of the 15th Euro. Work., on Comp. Geo. (1999)"},{"key":"21_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0747-7171(89)80002-1","volume":"7","author":"H.W. Scholten","year":"1989","unstructured":"Scholten, H.W., Overmars, M.H.: General methods for adding range restrictions to decomposable searching problems. J. Symbolic Comput.\u00a07, 1\u201310 (1989)","journal-title":"J. Symbolic Comput."},{"key":"21_CR12","doi-asserted-by":"crossref","unstructured":"Boissonnat, J.D., Nullans, S.: Reconstruction of geometrical structure from heterogeneous and sparse data. In: ACM GIS (1996)","DOI":"10.1145\/258319.258363"},{"key":"21_CR13","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: An Introduction","author":"F.P. Preparata","year":"1985","unstructured":"Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction. Springer, New York (1985)"},{"issue":"1","key":"21_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1142\/S0218195996000022","volume":"6","author":"J.-D. Boissonnat","year":"1996","unstructured":"Boissonnat, J.-D., C\u00e9r\u00e9zo, A., Devillers, O., Teillaud, M.: Output-sensitive construction of the Delaunay triangulation of points lying in two planes. Internat. J. Comput. Geom. Appl.\u00a06(1), 1\u201314 (1996)","journal-title":"Internat. J. Comput. Geom. Appl."},{"key":"21_CR15","unstructured":"Chan, T.M., Snoeyink, J., Yap, C.-K.: Output-sensitive construction of polytopes in four dimensions and clipped Voronoi diagrams in three. In: Proc. 6th ACM-SIAM Sympos. Discrete Algorithms, pp. 282\u2013291 (1995)"},{"key":"21_CR16","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 4-d polytopes and 3-d Voronoi diagrams. Discrete Comput. Geom.\u00a018, 433\u2013454 (1997)","journal-title":"Discrete Comput. Geom."},{"key":"21_CR17","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/BF02712874","volume":"16","author":"T.M. Chan","year":"1996","unstructured":"Chan, T.M.: Output-sensitive results on convex hulls, extreme points, and related problems. Discrete Comput. Geom.\u00a016, 369\u2013387 (1996)","journal-title":"Discrete Comput. Geom."},{"issue":"l","key":"21_CR18","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1145\/321556.321564","volume":"17","author":"D.R. Chand","year":"1970","unstructured":"Chand, D.R., Kapur, S.S.: An algorithm for convex polytopes. J. ACM\u00a017(l), 78\u201386 (1970)","journal-title":"J. ACM"},{"issue":"3","key":"21_CR19","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/0020-0190(81)90111-3","volume":"12","author":"R.J. Fowler","year":"1981","unstructured":"Fowler, R.J., Paterson, M.S., Tanimoto, S.L.: Optimal packing and covering in the plane are NP-complete. Inform. Process. Lett.\u00a012(3), 133\u2013137 (1981)","journal-title":"Inform. Process. Lett."},{"key":"21_CR20","doi-asserted-by":"crossref","unstructured":"Efrat, A., Katz, M.J., Nielsen, F., Sharir, M.: Dynamic data structures for fat objects and their applications. In: Proc. 5th Workshop Algorithms Data Struct., pp. 297\u2013306 (1997)","DOI":"10.1007\/3-540-63307-3_69"},{"key":"21_CR21","doi-asserted-by":"crossref","unstructured":"Katz, M.J.: 3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects. Comput. Geom. Theory Appl. (to appear)","DOI":"10.1016\/S0925-7721(96)00027-2"},{"key":"21_CR22","doi-asserted-by":"crossref","unstructured":"Efrat, A.: The complexity of the union of (\u03b1,\u03b2)-covered objects. In: Proc. of the ACM Symp. of Comp. Geo. (1999)","DOI":"10.1145\/304893.304958"}],"container-title":["Lecture Notes in Computer Science","Discrete and Computational Geometry"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-46515-7_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,5]],"date-time":"2019-06-05T12:47:55Z","timestamp":1559738875000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-46515-7_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540671817","9783540465157"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-46515-7_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2000]]}}}