{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T16:42:37Z","timestamp":1773247357605,"version":"3.50.1"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2020,7,13]],"date-time":"2020-07-13T00:00:00Z","timestamp":1594598400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,7,13]],"date-time":"2020-07-13T00:00:00Z","timestamp":1594598400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Knowl Inf Syst"],"published-print":{"date-parts":[[2020,10]]},"DOI":"10.1007\/s10115-020-01486-9","type":"journal-article","created":{"date-parts":[[2020,7,13]],"date-time":"2020-07-13T21:02:15Z","timestamp":1594674135000},"page":"4091-4111","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Efficient computation of the convex hull on sets of points stored in a k-tree compact data structure"],"prefix":"10.1007","volume":"62","author":[{"given":"Juan Felipe","family":"Castro","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Miguel","family":"Romero","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gilberto","family":"Guti\u00e9rrez","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1543-2378","authenticated-orcid":false,"given":"M\u00f3nica","family":"Caniup\u00e1n","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carlos","family":"Quijada-Fuentes","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,7,13]]},"reference":[{"issue":"5","key":"1486_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","journal-title":"Inf Process Lett"},{"issue":"4","key":"1486_CR2","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1145\/235815.235821","volume":"22","author":"B Barber","year":"1996","unstructured":"Barber B, Dobkin D, Huhdanpaa H (1996) The quickhull algorithm for convex hulls. ACM Trans Math Softw 22(4):469\u2013483","journal-title":"ACM Trans Math Softw"},{"key":"1486_CR3","doi-asserted-by":"crossref","unstructured":"B\u00f6hm C, Kriegel H-P (2001) Determining the convex hull in large multidimensional databases. In: Proceedings of the third international conference on data warehousing and knowledge discovery, pp 294\u2013306","DOI":"10.1007\/3-540-44801-2_29"},{"key":"1486_CR4","doi-asserted-by":"crossref","unstructured":"Brisaboa N, Ladra S, Navarro G (2009) k2-trees for compact web graph representation. In: Proceedings of the 16th international symposium on string processing and information retrieval, pp 18\u201330","DOI":"10.1007\/978-3-642-03784-9_3"},{"issue":"5","key":"1486_CR5","doi-asserted-by":"publisher","first-page":"635","DOI":"10.1016\/j.is.2013.01.005","volume":"38","author":"N Brisaboa","year":"2013","unstructured":"Brisaboa N, Luaces M, Navarro G, Seco D (2013) Space-efficient representations of rectangle datasets supporting orthogonal range querying. Inf Syst 38(5):635\u2013655","journal-title":"Inf Syst"},{"issue":"2","key":"1486_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1371\/journal.pone.0212189","volume":"14","author":"O Cadenas","year":"2019","unstructured":"Cadenas O, Megson GM (2019) Preprocessing 2d data for fast convex hull computations. PLoS ONE 14(2):1\u201315","journal-title":"PLoS ONE"},{"issue":"2","key":"1486_CR7","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1007\/s10115-015-0908-6","volume":"49","author":"D Caro","year":"2016","unstructured":"Caro D, Rodr\u00edguez A, Brisaboa N, Fari\u00f1a A (2016) Compressed k$${}^{\\text{ d }}$$-tree for temporal graphs. Knowl Inf Syst 49(2):553\u2013595","journal-title":"Knowl Inf Syst"},{"key":"1486_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational geometry: algorithms and applications","author":"M De Berg","year":"2008","unstructured":"De Berg M, Cheong O, Van Kreveld M, Overmars M (2008) Computational geometry: algorithms and applications. Springer, Berlin"},{"key":"1486_CR9","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/j.tcs.2015.03.011","volume":"581","author":"S Durocher","year":"2015","unstructured":"Durocher S, El-Zein H, Lan Munro J, Thankachan S (2015) Low space data structures for geometric range mode query. Theor Comput Sci 581:97\u2013101","journal-title":"Theor Comput Sci"},{"issue":"4","key":"1486_CR10","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1016\/0020-0190(72)90045-2","volume":"1","author":"R Graham","year":"1972","unstructured":"Graham R (1972) An efficient algorithm for determining the convex hull of a finite planar set. Inf Proces Lett 1(4):132\u2013133","journal-title":"Inf Proces Lett"},{"key":"1486_CR11","doi-asserted-by":"crossref","unstructured":"Guttman A (1984) R-trees: a dynamic index structure for spatial searching. In: Proceedings of the 1984 ACM SIGMOD international conference on management of data, pp 47\u201357","DOI":"10.1145\/971697.602266"},{"issue":"4","key":"1486_CR12","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1016\/0196-6774(83)90013-5","volume":"4","author":"R Graham","year":"1983","unstructured":"Graham R, Yao F (1983) Finding the convex hull of a simple polygon. J Algorithms 4(4):324\u2013331","journal-title":"J Algorithms"},{"issue":"1","key":"1486_CR13","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/0020-0190(73)90020-3","volume":"2","author":"R Jarvis","year":"1973","unstructured":"Jarvis R (1973) On the identification of the convex hull of a finite set of points in the plane. Inf Process Lett 2(1):18\u201321","journal-title":"Inf Process Lett"},{"issue":"1","key":"1486_CR14","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1137\/0215021","volume":"15","author":"D Kirkpatrick","year":"1986","unstructured":"Kirkpatrick D, Seidel R (1986) The ultimate planar convex hull algorithm. SIAM J Comput 15(1):287\u2013299","journal-title":"SIAM J Comput"},{"issue":"1","key":"1486_CR15","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1016\/j.neucom.2011.09.011","volume":"77","author":"R Liu","year":"2012","unstructured":"Liu R, Fang B, Tang Y, Wen J, Qian J (2012) A fast convex hull algorithm with maximum inscribed circle affine transformation. Neurocomputing 77(1):212\u2013221","journal-title":"Neurocomputing"},{"issue":"1","key":"1486_CR16","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/0167-8655(85)90039-X","volume":"3","author":"M Mcqueen","year":"1985","unstructured":"Mcqueen M, Toussaint G (1985) On the ultimate convex hull algorithm in practice. Pattern Recogn Lett 3(1):29\u201334","journal-title":"Pattern Recogn Lett"},{"key":"1486_CR17","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804120","volume-title":"Computational geometry in C","author":"J O\u2019Rourke","year":"1998","unstructured":"O\u2019Rourke J (1998) Computational geometry in C, 2nd edn. Cambridge University Press, Cambridge, New York","edition":"2"},{"issue":"2","key":"1486_CR18","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1145\/359423.359430","volume":"20","author":"F Preparata","year":"1977","unstructured":"Preparata F, Hong SJ (1977) Convex hulls of finite sets of points in two and three dimensions. Commun ACM 20(2):87\u201393","journal-title":"Commun ACM"},{"key":"1486_CR19","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational geometry: an introduction","author":"F Preparata","year":"1985","unstructured":"Preparata F, Shamos M (1985) Computational geometry: an introduction. Springer, New York"},{"key":"1486_CR20","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-19363-7","volume-title":"In-memory data management: an inflection point for enterprise applications","author":"H Plattner","year":"2011","unstructured":"Plattner H, Zeier A (2011) In-memory data management: an inflection point for enterprise applications, 1st edn. Springer, Berlin","edition":"1"},{"key":"1486_CR21","doi-asserted-by":"crossref","unstructured":"Raman R, Raman V, Rao SS, (2001) Succinct dynamic data structures. In: Dehne F, Sack JR, Tamassia R (eds) Algorithms and data structures. WADS, (2001) Lecture Notes in Computer Science, vol 2125. Springer, Berlin, Heidelberg, pp 426\u2013437","DOI":"10.1007\/3-540-44634-6_39"},{"issue":"2","key":"1486_CR22","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1023\/A:1009745219419","volume":"2","author":"J Sander","year":"1998","unstructured":"Sander J, Ester M, Kriegel H-P, Xiaowei X (1998) Density-based clustering in spatial databases: the algorithm gdbscan and its applications. Data Min Knowl Discov 2(2):169\u2013194","journal-title":"Data Min Knowl Discov"},{"issue":"2","key":"1486_CR23","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/0167-8655(82)90016-2","volume":"1","author":"J Sklansky","year":"1982","unstructured":"Sklansky J (1982) Finding the convex hull of a simple polygon. Pattern Recogn Lett 1(2):79\u201383","journal-title":"Pattern Recogn Lett"}],"container-title":["Knowledge and Information Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10115-020-01486-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10115-020-01486-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10115-020-01486-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,12]],"date-time":"2021-07-12T23:11:41Z","timestamp":1626131501000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10115-020-01486-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,13]]},"references-count":23,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2020,10]]}},"alternative-id":["1486"],"URL":"https:\/\/doi.org\/10.1007\/s10115-020-01486-9","relation":{},"ISSN":["0219-1377","0219-3116"],"issn-type":[{"value":"0219-1377","type":"print"},{"value":"0219-3116","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,7,13]]},"assertion":[{"value":"11 October 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 July 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 July 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}