{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:33:00Z","timestamp":1759638780861,"version":"3.40.3"},"publisher-location":"Cham","reference-count":24,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319623887"},{"type":"electronic","value":"9783319623894"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-62389-4_4","type":"book-chapter","created":{"date-parts":[[2017,6,30]],"date-time":"2017-06-30T15:07:46Z","timestamp":1498835266000},"page":"38-49","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Depth Distribution in High Dimensions"],"prefix":"10.1007","author":[{"given":"J\u00e9r\u00e9my","family":"Barbay","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pablo","family":"P\u00e9rez-Lantero","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Javiel","family":"Rojas-Ledesma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,7,1]]},"reference":[{"key":"4_CR1","unstructured":"Khamis, M.A., Ngo, H.Q., R\u00e9, C., Rudra, A.: Joins via geometric resolutions: worst-case and beyond. In: Proceedings of the 34th ACM Symposium on Principles of Database Systems (PODS), Melbourne, Victoria, Australia, 31 May\u20134 June, 2015, pp. 213\u2013228 (2015)"},{"key":"4_CR2","doi-asserted-by":"crossref","unstructured":"Afshani, P.: Fast computation of output-sensitive maxima in a word RAM. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Portland, Oregon, USA, January 5\u20137, 2014, pp. 1414\u20131423. SIAM (2014)","DOI":"10.1137\/1.9781611973402.104"},{"key":"4_CR3","doi-asserted-by":"crossref","unstructured":"Afshani, P., Arge, L., Larsen, K.G.: Higher-dimensional orthogonal range reporting and rectangle stabbing in the pointer machine model. In: Symposuim on Computational Geometry (SoCG), Chapel Hill, NC, USA, June 17\u201320, 2012, pp. 323\u2013332 (2012)","DOI":"10.1145\/2261250.2261299"},{"issue":"1","key":"4_CR4","doi-asserted-by":"publisher","first-page":"3:1","DOI":"10.1145\/3046673","volume":"64","author":"P Afshani","year":"2017","unstructured":"Afshani, P., Barbay, J., Chan, T.M.: Instance-optimal geometric algorithms. J. ACM (JACM) 64(1), 3:1\u20133:38 (2017)","journal-title":"J. ACM (JACM)"},{"key":"4_CR5","doi-asserted-by":"crossref","unstructured":"Barbay, J., P\u00e9rez-Lantero, P., Rojas-Ledesma, J.: Depth distribution in high dimension. ArXiv e-prints (2017)","DOI":"10.1007\/978-3-319-62389-4_4"},{"key":"4_CR6","unstructured":"Bentley, J.L.: Algorithms for Klee\u2019s rectangle problems. Unpublished notes (1977)"},{"issue":"5\u20136","key":"4_CR7","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/j.comgeo.2011.12.001","volume":"45","author":"K Bringmann","year":"2012","unstructured":"Bringmann, K.: An improved algorithm for Klee\u2019s measure problem on fat boxes. Comput. Geom. Theor. Appl. 45(5\u20136), 225\u2013233 (2012)","journal-title":"Comput. Geom. Theor. Appl."},{"key":"4_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/978-3-642-40313-2_20","volume-title":"Mathematical Foundations of Computer Science 2013","author":"K Bringmann","year":"2013","unstructured":"Bringmann, K.: Bringing order to special cases of Klee\u2019s measure problem. In: Chatterjee, K., Sgall, J. (eds.) MFCS 2013. LNCS, vol. 8087, pp. 207\u2013218. Springer, Heidelberg (2013). doi:10.1007\/978-3-642-40313-2_20"},{"key":"4_CR9","unstructured":"Chan, T.M.: A (slightly) faster algorithm for Klee\u2019s Measure Problem. In: Proceedings of the 24th ACM Symposium on Computational Geometry (SoCG), College Park, MD, USA, June 9\u201311, 2008, pp. 94\u2013100 (2008)"},{"key":"4_CR10","doi-asserted-by":"crossref","unstructured":"Chan, T.M.: Klee\u2019s measure problem made easy. In: 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Berkeley, CA, USA, 26\u201329 October, 2013, pp. 410\u2013419 (2013)","DOI":"10.1109\/FOCS.2013.51"},{"key":"4_CR11","doi-asserted-by":"crossref","unstructured":"Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. In: Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC), New York, USA, pp. 1\u20136. ACM (1987)","DOI":"10.1145\/28395.28396"},{"key":"4_CR12","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009)","edition":"3"},{"issue":"3","key":"4_CR13","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/BF02238431","volume":"55","author":"F d\u2019Amore","year":"1995","unstructured":"d\u2019Amore, F., Nguyen, V.H., Roos, T., Widmayer, P.: On optimal cuts of hyperrectangles. Computing 55(3), 191\u2013206 (1995)","journal-title":"Computing"},{"issue":"3\u20134","key":"4_CR14","first-page":"209","volume":"13","author":"H Edelsbrunner","year":"1983","unstructured":"Edelsbrunner, H.: A new approach to rectangle intersections part I. J. Comput. Math. (JCM) 13(3\u20134), 209\u2013219 (1983)","journal-title":"J. Comput. Math. (JCM)"},{"issue":"7","key":"4_CR15","doi-asserted-by":"publisher","first-page":"540","DOI":"10.1145\/359545.359553","volume":"21","author":"ML Fredman","year":"1978","unstructured":"Fredman, M.L., Weide, B.W.: On the complexity of computing the measure of $$\\cup ^{n}_1 [a_i; b_i]$$. Commun. ACM (CACM) 21(7), 540\u2013544 (1978)","journal-title":"Commun. ACM (CACM)"},{"key":"4_CR16","unstructured":"Gall, F.L.: Powers of tensors and fast matrix multiplication. In: International Symposium on Symbolic and Algebraic Computation (ISSAC), Kobe, Japan, July 23\u201325, 2014, pp. 296\u2013303. ACM (2014)"},{"key":"4_CR17","doi-asserted-by":"crossref","unstructured":"Kirkpatrick, D.G., Seidel, R.: Output-size sensitive algorithms for finding maximal vectors. In: Proceedings of the First Annual Symposium on Computational Geometry (SoCG), Baltimore, Maryland, USA, June 5\u20137, 1985, pp. 89\u201396 (1985)","DOI":"10.1145\/323233.323246"},{"issue":"4","key":"4_CR18","doi-asserted-by":"publisher","first-page":"284","DOI":"10.2307\/2318871","volume":"84","author":"V Klee","year":"1977","unstructured":"Klee, V.: Can the measure of $$\\cup ^{n}_1 [a_i; b_i]$$ be computed in less than O(n log n) steps? Am. Math. Mon. (AMM) 84(4), 284\u2013285 (1977)","journal-title":"Am. Math. Mon. (AMM)"},{"key":"4_CR19","doi-asserted-by":"publisher","first-page":"1082","DOI":"10.4153\/CJM-1970-125-1","volume":"22","author":"DR Lick","year":"1970","unstructured":"Lick, D.R., White, A.T.: k-Degenerate graphs. Can. J. Math. (CJM) 22, 1082\u20131096 (1970)","journal-title":"Can. J. Math. (CJM)"},{"issue":"3","key":"4_CR20","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1145\/2402.322385","volume":"30","author":"DW Matula","year":"1983","unstructured":"Matula, D.W., Beck, L.L.: Smallest-last ordering and clustering and graph coloring algorithms. J. ACM (JACM) 30(3), 417\u2013427 (1983)","journal-title":"J. ACM (JACM)"},{"issue":"2","key":"4_CR21","first-page":"70","volume":"24","author":"A Moffat","year":"1992","unstructured":"Moffat, A., Petersson, O.: An overview of adaptive sorting. Aust. Comput. J. (ACJ) 24(2), 70\u201377 (1992)","journal-title":"Aust. Comput. J. (ACJ)"},{"issue":"6","key":"4_CR22","doi-asserted-by":"publisher","first-page":"1034","DOI":"10.1137\/0220065","volume":"20","author":"MH Overmars","year":"1991","unstructured":"Overmars, M.H., Yap, C.: New upper bounds in Klee\u2019s measure problem. SIAM J. Comput. (SICOMP) 20(6), 1034\u20131045 (1991)","journal-title":"SIAM J. Comput. (SICOMP)"},{"issue":"4","key":"4_CR23","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1007\/BF02165411","volume":"13","author":"V Strassen","year":"1969","unstructured":"Strassen, V.: Gaussian elimination is not optimal. Numer. Math. 13(4), 354\u2013356 (1969)","journal-title":"Numer. Math."},{"key":"4_CR24","unstructured":"Yildiz, H., Hershberger, J., Suri, S.: A discrete and dynamic version of Klee\u2019s measure problem. In: Proceedings of the 23rd Annual Canadian Conference on Computational Geometry (CCCG), Toronto, Ontario, Canada, August 10\u201312, 2011 (2011)"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-62389-4_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T11:22:43Z","timestamp":1709810563000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-62389-4_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319623887","9783319623894"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-62389-4_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]},"assertion":[{"value":"1 July 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOON","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computing and Combinatorics Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Hong Kong","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2017","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 August 2017","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 August 2017","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoon2017","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/cocoon2017.comp.polyu.edu.hk\/index.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}