{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,2]],"date-time":"2025-08-02T19:21:01Z","timestamp":1754162461336,"version":"3.41.2"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,2,26]],"date-time":"2025-02-26T00:00:00Z","timestamp":1740528000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,2,26]],"date-time":"2025-02-26T00:00:00Z","timestamp":1740528000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Geoinformatica"],"published-print":{"date-parts":[[2025,7]]},"DOI":"10.1007\/s10707-025-00538-y","type":"journal-article","created":{"date-parts":[[2025,2,26]],"date-time":"2025-02-26T00:19:31Z","timestamp":1740529171000},"page":"517-545","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An in-place Quickhull algorithm"],"prefix":"10.1007","volume":"29","author":[{"given":"Kyuseo","family":"Park","sequence":"first","affiliation":[]},{"given":"Markus","family":"Schneider","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,2,26]]},"reference":[{"issue":"5","key":"538_CR1","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0020-0190(78)90003-0","volume":"7","author":"SG Akl","year":"1978","unstructured":"Akl SG, Toussaint GT (1978) A fast convex hull algorithm. Inf Process Lett 7(5):219\u2013222. https:\/\/doi.org\/10.1016\/0020-0190(78)90003-0","journal-title":"Inf Process Lett"},{"issue":"5","key":"538_CR2","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1016\/0020-0190(79)90072-3","volume":"9","author":"AM Andrew","year":"1979","unstructured":"Andrew AM (1979) Another efficient algorithm for convex hulls in two dimensions. Inf Process Lett 9(5):216\u2013219. https:\/\/doi.org\/10.1016\/0020-0190(79)90072-3","journal-title":"Inf Process Lett"},{"issue":"3","key":"538_CR3","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1016\/0262-8856(83)90065-3","volume":"1","author":"BK Bhattacharya","year":"1983","unstructured":"Bhattacharya BK, Toussaint GT (1983) Time- and storage-efficient implementation of an optimal planar convex hull algorithm. Image Vis Comput 1(3):140\u2013144. https:\/\/doi.org\/10.1016\/0262-8856(83)90065-3","journal-title":"Image Vis Comput"},{"issue":"1","key":"538_CR4","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.tcs.2003.05.004","volume":"321","author":"H Br\u00f6nnimann","year":"2004","unstructured":"Br\u00f6nnimann H, Iacono J, Katajainen J et al (2004) Space-efficient planar convex hull algorithms. Theor Comput Sci 321(1):25\u201340. https:\/\/doi.org\/10.1016\/j.tcs.2003.05.004","journal-title":"Theor Comput Sci"},{"issue":"6","key":"538_CR5","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1016\/0020-0190(78)90021-2","volume":"7","author":"A Bykat","year":"1978","unstructured":"Bykat A (1978) Convex hull of a finite set of points in two dimensions. Inf Process Lett 7(6):296\u2013298. https:\/\/doi.org\/10.1016\/0020-0190(78)90021-2","journal-title":"Inf Process Lett"},{"issue":"4","key":"538_CR6","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1007\/BF02712873","volume":"16","author":"TM Chan","year":"1996","unstructured":"Chan TM (1996) Optimal output-sensitive convex hull algorithms in two and three dimensions. Discrete & Computational Geometry 16(4):361\u2013368. https:\/\/doi.org\/10.1007\/BF02712873","journal-title":"Discrete & Computational Geometry"},{"key":"538_CR7","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/PL00009327","volume":"18","author":"TM Chan","year":"1997","unstructured":"Chan TM, Snoeyink J, Yap C (1997) Primal dividing and dual pruning: Output-sensitive construction of four-dimensional polytopes and three-dimensional voronoi diagrams. Discrete & Computational Geometry 18:433\u2013454. https:\/\/doi.org\/10.1007\/PL00009327","journal-title":"Discrete & Computational Geometry"},{"key":"538_CR8","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1007\/BF02237955","volume":"26","author":"L Devroye","year":"1981","unstructured":"Devroye L, Toussaint GT (1981) A note on linear expected time algorithms for finding convex hulls. Computing 26:361\u2013366. https:\/\/doi.org\/10.1007\/BF02237955","journal-title":"Computing"},{"issue":"4","key":"538_CR9","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1145\/355759.355766","volume":"3","author":"WF Eddy","year":"1977","unstructured":"Eddy WF (1977) A new convex hull algorithm for planar sets. ACM Trans on Mathematical Software 3(4):398\u2013403. https:\/\/doi.org\/10.1145\/355759.355766","journal-title":"ACM Trans on Mathematical Software"},{"issue":"12","key":"538_CR10","doi-asserted-by":"publisher","first-page":"195","DOI":"10.3390\/a11120195","volume":"11","author":"AN Gamby","year":"2018","unstructured":"Gamby AN, Katajainen J (2018) Convex-hull algorithms: Implementation, testing, and experimentation. Algorithms 11(12):195. https:\/\/doi.org\/10.3390\/a11120195","journal-title":"Algorithms"},{"key":"538_CR11","unstructured":"Gamby AN, Katajainen J (2018b) Convex-hull algorithms in C++. http:\/\/hjemmesider.diku.dk\/~jyrki\/Myris\/GK2018S.html"},{"key":"538_CR12","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/j.cad.2015.07.013","volume":"70","author":"AJP Gomes","year":"2016","unstructured":"Gomes AJP (2016) A total order heuristic-based convex hull algorithm for points in the plane. Comput Aided Des 70:153\u2013160. https:\/\/doi.org\/10.1016\/j.cad.2015.07.013","journal-title":"Comput Aided Des"},{"issue":"4","key":"538_CR13","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1016\/0020-0190(72)90045-2","volume":"1","author":"RL Graham","year":"1972","unstructured":"Graham RL (1972) An efficient algorithm for determining the convex hull of a finite planar set. Inf Process Lett 1(4):132\u2013133. https:\/\/doi.org\/10.1016\/0020-0190(72)90045-2","journal-title":"Inf Process Lett"},{"key":"538_CR14","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/s10013-014-0067-1","volume":"43","author":"ND Ho\u00e0ng","year":"2015","unstructured":"Ho\u00e0ng ND, Linh NK (2015) Quicker than quickhull. Vietnam J Math 43:57\u201370. https:\/\/doi.org\/10.1007\/s10013-014-0067-1","journal-title":"Vietnam J Math"},{"issue":"1","key":"538_CR15","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1137\/0215021","volume":"15","author":"DG Kirkpatrick","year":"1986","unstructured":"Kirkpatrick DG, Seidel R (1986) The ultimate planar convex-hull algorithm? SIAM Journal of Computing 15(1):287\u2013299. https:\/\/doi.org\/10.1137\/0215021","journal-title":"SIAM Journal of Computing"},{"key":"538_CR16","unstructured":"Vahrenhold J (2012) On the space efficiency of the ultimate planar convex hull algorithm. Can Conf Comput Geom pp 131\u2013136. http:\/\/2012.cccg.ca\/papers\/paper51.pdf"}],"container-title":["GeoInformatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10707-025-00538-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10707-025-00538-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10707-025-00538-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T07:28:27Z","timestamp":1753860507000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10707-025-00538-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,26]]},"references-count":16,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,7]]}},"alternative-id":["538"],"URL":"https:\/\/doi.org\/10.1007\/s10707-025-00538-y","relation":{},"ISSN":["1384-6175","1573-7624"],"issn-type":[{"type":"print","value":"1384-6175"},{"type":"electronic","value":"1573-7624"}],"subject":[],"published":{"date-parts":[[2025,2,26]]},"assertion":[{"value":"1 June 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 December 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 February 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 February 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no Conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}