{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,22]],"date-time":"2026-01-22T03:45:56Z","timestamp":1769053556976,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":36,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540434009","type":"print"},{"value":"9783540459958","type":"electronic"}],"license":[{"start":{"date-parts":[[2002,1,1]],"date-time":"2002-01-01T00:00:00Z","timestamp":1009843200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45995-2_43","type":"book-chapter","created":{"date-parts":[[2007,5,30]],"date-time":"2007-05-30T02:33:34Z","timestamp":1180492414000},"page":"494-507","source":"Crossref","is-referenced-by-count":6,"title":["In-Place Planar Convex Hull Algorithms"],"prefix":"10.1007","author":[{"given":"Herv\u00e9","family":"Br\u00f6nnimann","sequence":"first","affiliation":[]},{"given":"John","family":"Iacono","sequence":"additional","affiliation":[]},{"given":"Jyrki","family":"Katajainen","sequence":"additional","affiliation":[]},{"given":"Pat","family":"Morin","sequence":"additional","affiliation":[]},{"given":"Jason","family":"Morrison","sequence":"additional","affiliation":[]},{"given":"Godfried","family":"Toussaint","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,3,14]]},"reference":[{"key":"43_CR1","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1016\/0020-0190(79)90072-3","volume":"9","author":"A. M. Andrew","year":"1979","unstructured":"A. M. Andrew. Another efficient algorithm for convex hulls in two dimensions. Information Processing Letters, 9:216\u2013219, 1979. Corrigendum, Information Processing Letters, 10:168, 1980.","journal-title":"Information Processing Letters"},{"issue":"1","key":"43_CR2","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1006\/jagm.1997.0869","volume":"25","author":"B. K. Bhattacharya","year":"1997","unstructured":"B. K. Bhattacharya and S. Sen. On a simple, practical, optimal, output-sensitive randomized planar convex hull algorithm. Journal of Algorithms, 25(1):177\u2013193, 1997.","journal-title":"Journal of Algorithms"},{"key":"43_CR3","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1007\/BF02712873","volume":"16","author":"T. Chan","year":"1996","unstructured":"T. Chan. Optimal output-sensitive convex hull algorithms in two and three dimensions. Discrete & Computational Geometry, 16:361\u2013368, 1996.","journal-title":"Discrete & Computational Geometry"},{"key":"43_CR4","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/PL00009327","volume":"18","author":"T. Chan","year":"1997","unstructured":"T. Chan, J. Snoeyink, and C. K. Yap. Primal dividing and dual pruning: Output-sensitive construction of four-dimensional polytopes and threedimensional Voronoi diagrams. Discrete & Computational Geometry, 18:433\u2013454, 1997.","journal-title":"Discrete & Computational Geometry"},{"key":"43_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/7531.24036","volume":"34","author":"B. Chazelle","year":"1987","unstructured":"B. Chazelle and D. P. Dobkin. Intersection of convex objects in 2 and 3 dimensions. Journal of the ACM, 34:1\u201327, 1987.","journal-title":"Journal of the ACM"},{"issue":"1","key":"43_CR6","first-page":"387","volume":"4","author":"K. L. Clarkson","year":"1988","unstructured":"K. L. Clarkson and P. W. Shor. Applications of random sampling in computational geometry, II. Discrete & Computational Geometry, 4(1):387\u2013421, 1988.","journal-title":"Discrete & Computational Geometry"},{"issue":"3","key":"43_CR7","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/0167-6423(82)90016-8","volume":"1","author":"E.W. Dijkstra","year":"1982","unstructured":"E.W. Dijkstra. Smoothsort, an alternative for sorting in situ. Science of Computer Programming, 1(3):223\u2013233, 1982.","journal-title":"Science of Computer Programming"},{"issue":"3","key":"43_CR8","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/0020-0190(82)90045-X","volume":"15","author":"E. W. Dijkstra","year":"1982","unstructured":"E. W. Dijkstra and A. J. M. van Gasteren. An introduction to three algorithms for sorting in situ. Information Processing Letters, 15(3):129\u2013134, 1982.","journal-title":"Information Processing Letters"},{"issue":"4","key":"43_CR9","doi-asserted-by":"publisher","first-page":"372","DOI":"10.1093\/comjnl\/30.4.372","volume":"30","author":"S. Dvorak","year":"1987","unstructured":"S. Dvorak and B. Durian. Stable linear time sublinear space merging. The Computer Journal, 30(4):372\u2013375, 1987.","journal-title":"The Computer Journal"},{"issue":"3","key":"43_CR10","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1093\/comjnl\/31.3.279","volume":"31","author":"S. Dvorak","year":"1988","unstructured":"S. Dvorak and B. Durian. Unstable linear time O(1) space merging. The Computer Journal, 31(3):279\u2013282, 1988.","journal-title":"The Computer Journal"},{"issue":"4","key":"43_CR11","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1145\/355759.355766","volume":"3","author":"W. Eddy","year":"1977","unstructured":"W. Eddy. A new convex hull algorithm for planar sets. ACM Transactions on Mathematical Software, 3(4):398\u2013403, 1977.","journal-title":"ACM Transactions on Mathematical Software"},{"key":"43_CR12","first-page":"401","volume":"7","author":"R. W. Floyd","year":"1964","unstructured":"R. W. Floyd. Algorithm 245, Treesort 3. Communications of the ACM, 7:401, 1964.","journal-title":"Communications of the ACM"},{"key":"43_CR13","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1016\/0020-0190(72)90045-2","volume":"1","author":"R. L. Graham","year":"1972","unstructured":"R. L. Graham. An efficient algorithm for determining the convex hull of a finite planar set. Information Processing Letters, 1:132\u2013133, 1972.","journal-title":"Information Processing Letters"},{"key":"43_CR14","unstructured":"E. Horowitz, S. Sahni, and S. Rajasekaran. Computer Algorithms. Computer Science Press, 1998."},{"issue":"3","key":"43_CR15","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1145\/42392.42403","volume":"31","author":"B.-C. Huang","year":"1988","unstructured":"B.-C. Huang and M. A. Langston. Practical in-place merging. Communications of the ACM, 31(3):348\u2013352, 1988.","journal-title":"Communications of the ACM"},{"issue":"6","key":"43_CR16","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1093\/comjnl\/35.6.643","volume":"35","author":"B.-C. Huang","year":"1992","unstructured":"B.-C. Huang and M. A. Langston. Fast stable merging and sorting in constant extrasp ace. The Computer Journal, 35(6):643\u2013650, 1992.","journal-title":"The Computer Journal"},{"key":"43_CR17","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/0020-0190(73)90020-3","volume":"2","author":"A. Jarvis","year":"1973","unstructured":"A. Jarvis. On the identification of the convex hull of a finite set of points in the plane. Information Processing Letters, 2:18\u201321, 1973.","journal-title":"Information Processing Letters"},{"key":"43_CR18","first-page":"27","volume":"3","author":"J. Katajainen","year":"1996","unstructured":"J. Katajainen, T. Pasanen, and J. Teuhola. Practical in-place mergesort. Nordic Journal of Computing, 3:27\u201340, 1996.","journal-title":"Nordic Journal of Computing"},{"issue":"4","key":"43_CR19","doi-asserted-by":"publisher","first-page":"580","DOI":"10.1007\/BF01994842","volume":"32","author":"J. Katajainen","year":"1992","unstructured":"J. Katajainen and T. A. Pasanen. Stable minimum space partitioning in linear time. BIT, 32(4):580\u2013585, 1992.","journal-title":"BIT"},{"issue":"1","key":"43_CR20","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/S0020-0190(99)00038-1","volume":"70","author":"J. Katajainen","year":"1999","unstructured":"J. Katajainen and T. A. Pasanen. In-place sorting with fewer moves. Information Processing Letters, 70(1):31\u201337, 1999.","journal-title":"Information Processing Letters"},{"issue":"1","key":"43_CR21","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1137\/0215021","volume":"15","author":"D. G. Kirkpatrick","year":"1986","unstructured":"D. G. Kirkpatrick and R. Seidel. The ultimate planar convex hull algorithm? SIAM Journal on Computing, 15(1):287\u2013299, 1986.","journal-title":"SIAM Journal on Computing"},{"key":"43_CR22","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1007\/3-540-19487-8_2","volume-title":"Implicit selection","author":"T. W. Lai","year":"1988","unstructured":"T. W. Lai and D. Wood. Implicit selection. In Proceedings of the 1st Scandinavian Workshop on Algorithm Theory, volume 318 of Lecture Notes in Computer Science, pages 14\u201323. Springer-Verlag, 1988."},{"issue":"4","key":"43_CR23","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/0020-0190(84)90112-1","volume":"18","author":"H. Mannila","year":"1984","unstructured":"H. Mannila and E. Ukkonen. A simple linear-time algorithm for in situ merging. Information Processing Letters, 18(4):203\u2013208, 1984.","journal-title":"Information Processing Letters"},{"issue":"1","key":"43_CR24","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1145\/2422.322418","volume":"31","author":"N. Megiddo","year":"1984","unstructured":"N. Megiddo. Linear programming in linear time when the dimension is fixed. Journal of the ACM, 31(1):114\u2013127, 1984.","journal-title":"Journal of the ACM"},{"key":"43_CR25","unstructured":"P. Morin. insitu.tgz. Available online at http:\/\/cgm.cs.mcgill.ca \/~morin\/, 2001."},{"issue":"2","key":"43_CR26","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1007\/BF02017344","volume":"30","author":"J. I. Munro","year":"1990","unstructured":"J. I. Munro, V. Raman, and J. S. Salowe. Stable in situ sorting and minimum data movement. BIT, 30(2):220\u2013234, 1990.","journal-title":"BIT"},{"key":"43_CR27","doi-asserted-by":"publisher","first-page":"402","DOI":"10.1145\/359131.359132","volume":"22","author":"F. P. Preparata","year":"1979","unstructured":"F. P. Preparata. An optimal real time algorithm for planar convex hulls. Communications of the ACM, 22:402\u2013405, 1979.","journal-title":"Communications of the ACM"},{"issue":"20","key":"43_CR28","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1145\/359423.359430","volume":"2","author":"F. P. Preparata","year":"1977","unstructured":"F. P. Preparata and S. J. Hong. Convex hulls of finite point sets in two and three dimensions. Communications of the ACM, 2(20):87\u201393, 1977.","journal-title":"Communications of the ACM"},{"key":"43_CR29","doi-asserted-by":"crossref","unstructured":"F. P. Preparata and M. I. Shamos. Computational Geometry. Springer-Verlag, 1985.","DOI":"10.1007\/978-1-4612-1098-6"},{"issue":"4","key":"43_CR30","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1016\/0196-6774(87)90050-2","volume":"8","author":"J. Salowe","year":"1987","unstructured":"J. Salowe and W. Steiger. Simplified stable merging tasks. Journal of Algorithms, 8(4):557\u2013571, 1987.","journal-title":"Journal of Algorithms"},{"key":"43_CR31","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1007\/BF02574699","volume":"6","author":"R. Seidel","year":"1991","unstructured":"R. Seidel. Small-dimensional linear programming and convex hulls made easy. Discrete & Computational Geometry, 6:423\u2013434, 1991.","journal-title":"Discrete & Computational Geometry"},{"key":"43_CR32","unstructured":"M. I. Shamos. Computational Geometry. PhD thesis, Yale University, 1978."},{"issue":"3","key":"43_CR33","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1093\/comjnl\/27.3.270","volume":"27","author":"H. W. Six","year":"1984","unstructured":"H. W. Six and L. Wegner. Sorting a random access file in situ. The Computer Journal, 27(3):270\u2013275, 1984.","journal-title":"The Computer Journal"},{"issue":"8","key":"43_CR34","doi-asserted-by":"publisher","first-page":"681","DOI":"10.1093\/comjnl\/38.8.681","volume":"38","author":"A. Symvonis","year":"1995","unstructured":"A. Symvonis. Optimal stable merging. The Computer Journal, 38(8):681\u2013690, 1995.","journal-title":"The Computer Journal"},{"key":"43_CR35","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1007\/BF02523195","volume":"17","author":"R. Wenger","year":"1997","unstructured":"R. Wenger. Randomized quick hull.Algorithmica, 17:322\u2013329, 1997.","journal-title":"Algorithmica"},{"key":"43_CR36","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1145\/512274.512284","volume":"7","author":"J. W. J. Williams","year":"1964","unstructured":"J. W. J. Williams. Algorithm 232, Heapsort. Communications of the ACM, 7:347\u2013348, 1964.","journal-title":"Communications of the ACM"}],"container-title":["Lecture Notes in Computer Science","LATIN 2002: Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45995-2_43","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,14]],"date-time":"2021-08-14T09:39:53Z","timestamp":1628933993000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45995-2_43"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540434009","9783540459958"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/3-540-45995-2_43","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2002]]}}}