{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T18:57:37Z","timestamp":1778871457051,"version":"3.51.4"},"reference-count":64,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2017,2,28]],"date-time":"2017-02-28T00:00:00Z","timestamp":1488240000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100007277","name":"Center for Massive Data Algorithmics","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100007277","id-type":"DOI","asserted-by":"crossref"}]},{"name":"project Fondecyt Regular","award":["1170366"],"award-info":[{"award-number":["1170366"]}]},{"DOI":"10.13039\/501100001732","name":"Danish National Research Foundation","doi-asserted-by":"crossref","award":["DNRF84"],"award-info":[{"award-number":["DNRF84"]}],"id":[{"id":"10.13039\/501100001732","id-type":"DOI","asserted-by":"crossref"}]},{"name":"NSERC Discovery"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2017,2,28]]},"abstract":"<jats:p>\n            We prove the existence of an algorithm\n            <jats:italic>A<\/jats:italic>\n            for computing 2D or 3D convex hulls that is optimal for\n            <jats:italic>every point set<\/jats:italic>\n            in the following sense: for every sequence \u03c3 of\n            <jats:italic>n<\/jats:italic>\n            points and for every algorithm\n            <jats:italic>A<\/jats:italic>\n            \u2032 in a certain class\n            <jats:italic>A<\/jats:italic>\n            , the running time of\n            <jats:italic>A<\/jats:italic>\n            on input \u03c3 is at most a constant factor times the running time of\n            <jats:italic>A<\/jats:italic>\n            \u2032 on the worst possible permutation of \u03c3 for\n            <jats:italic>A<\/jats:italic>\n            \u2032. In fact, we can establish a stronger property: for every sequence \u03c3 of points and every algorithm\n            <jats:italic>A<\/jats:italic>\n            \u2032, the running time of\n            <jats:italic>A<\/jats:italic>\n            on \u03c3 is at most a constant factor times the average running time of\n            <jats:italic>A<\/jats:italic>\n            \u2032 over all permutations of \u03c3. We call algorithms satisfying these properties\n            <jats:italic>instance optimal<\/jats:italic>\n            in the\n            <jats:italic>order-oblivious<\/jats:italic>\n            and\n            <jats:italic>random-order<\/jats:italic>\n            setting. Such instance-optimal algorithms simultaneously subsume output-sensitive algorithms and distribution-dependent average-case algorithms, and all algorithms that do not take advantage of the order of the input or that assume the input are given in a random order.\n          <\/jats:p>\n          <jats:p>\n            The class\n            <jats:italic>A<\/jats:italic>\n            under consideration consists of all algorithms in a decision tree model where the tests involve only\n            <jats:italic>multilinear<\/jats:italic>\n            functions with a constant number of arguments. To establish an instance-specific lower bound, we deviate from traditional Ben-Or-style proofs and adopt a new adversary argument. For 2D convex hulls, we prove that a version of the well-known algorithm by Kirkpatrick and Seidel [1986] or Chan, Snoeyink, and Yap [1995] already attains this lower bound. For 3D convex hulls, we propose a new algorithm.\n          <\/jats:p>\n          <jats:p>\n            We further obtain instance-optimal results for a few other standard problems in computational geometry, such as maxima in 2D and 3D, orthogonal line segment intersection in 2D, finding bichromatic\n            <jats:italic>L<\/jats:italic>\n            <jats:sub>\u221e<\/jats:sub>\n            -close pairs in 2D, offline orthogonal range searching in 2D, offline dominance reporting in 2D and 3D, offline half-space range reporting in 2D and 3D, and offline point location in 2D. Our framework also reveals a connection to distribution-sensitive data structures and yields new results as a byproduct, for example, on online orthogonal range searching in 2D and online half-space range reporting in 2D and 3D.\n          <\/jats:p>","DOI":"10.1145\/3046673","type":"journal-article","created":{"date-parts":[[2017,3,20]],"date-time":"2017-03-20T12:29:43Z","timestamp":1490012983000},"page":"1-38","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Instance-Optimal Geometric Algorithms"],"prefix":"10.1145","volume":"64","author":[{"given":"Peyman","family":"Afshani","sequence":"first","affiliation":[{"name":"MADALGO, University of Aarhus, Aarhus N, Denmark"}]},{"given":"J\u00e9r\u00e9my","family":"Barbay","sequence":"additional","affiliation":[{"name":"DCC, Universidad de Chile, Santiago, Chile"}]},{"given":"Timothy M.","family":"Chan","sequence":"additional","affiliation":[{"name":"University of Waterloo"}]}],"member":"320","published-online":{"date-parts":[[2017,3,17]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Chan","author":"Afshani Peyman","year":"2009","unstructured":"Peyman Afshani and Timothy M . Chan . 2009 . Optimal halfspace range reporting in three dimensions. In Proc. 20th ACM-SIAM Symposium on Discrete Algorithms. 180--186. Peyman Afshani and Timothy M. Chan. 2009. Optimal halfspace range reporting in three dimensions. In Proc. 20th ACM-SIAM Symposium on Discrete Algorithms. 180--186."},{"key":"e_1_2_1_2_1","volume-title":"Agarwal and Jeff Erickson","author":"Pankaj","year":"1999","unstructured":"Pankaj K. Agarwal and Jeff Erickson . 1999 . Geometric range searching and its relatives. In Advances in Discrete and Computational Geometry, B. Chazelle, J. E. Goodman, and R. Pollack (Eds.). Contemporary Mathematics, Vol. 223 . American Mathematical Society , Providence, RI, 1--56. Pankaj K. Agarwal and Jeff Erickson. 1999. Geometric range searching and its relatives. In Advances in Discrete and Computational Geometry, B. Chazelle, J. E. Goodman, and R. Pollack (Eds.). Contemporary Mathematics, Vol. 223. American Mathematical Society, Providence, RI, 1--56."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/090766437"},{"key":"e_1_2_1_4_1","volume-title":"Proc. 6th International Symposium on Spatial Data Handling. 709--724","author":"Andrews D. S.","year":"1994","unstructured":"D. S. Andrews , Jack Snoeyink , Jim Boritz , Timothy M. Chan , Graham Denham , Jenny Harrison , and Chong Zhu . 1994 . Further comparisons of algorithms for geometric intersection problems . In Proc. 6th International Symposium on Spatial Data Handling. 709--724 . D. S. Andrews, Jack Snoeyink, Jim Boritz, Timothy M. Chan, Graham Denham, Jenny Harrison, and Chong Zhu. 1994. Further comparisons of algorithms for geometric intersection problems. In Proc. 6th International Symposium on Spatial Data Handling. 709--724."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1240233.1240240"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704446724"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195905001737"},{"key":"e_1_2_1_8_1","volume-title":"Proc. 20th Canadian Conference on Computational Geometry. 47--50","author":"Barbay J\u00e9r\u00e9my","year":"2008","unstructured":"J\u00e9r\u00e9my Barbay and Eric Chen . 2008 . Adaptive planar convex hull algorithm for a set of convex hulls . In Proc. 20th Canadian Conference on Computational Geometry. 47--50 . J\u00e9r\u00e9my Barbay and Eric Chen. 2008. Adaptive planar convex hull algorithm for a set of convex hulls. In Proc. 20th Canadian Conference on Computational Geometry. 47--50."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808735"},{"key":"e_1_2_1_10_1","volume-title":"Levine","author":"Bentley Jon Louis","year":"1990","unstructured":"Jon Louis Bentley , Kenneth L. Clarkson , and David B . Levine . 1990 . Fast linear expected-time algorithms for computing maxima and convex hulls. In Proc. 1st ACM-SIAM Symposium on Discrete Algorithms. 179--187. Jon Louis Bentley, Kenneth L. Clarkson, and David B. Levine. 1990. Fast linear expected-time algorithms for computing maxima and convex hulls. In Proc. 1st ACM-SIAM Symposium on Discrete Algorithms. 179--187."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0869"},{"key":"e_1_2_1_12_1","volume-title":"Odds-on trees. arXiv abs\/1002.1092","author":"Bose Prosenjit","year":"2010","unstructured":"Prosenjit Bose , Luc Devroye , Karim Dou\u00efeb , Vida Dujmovi\u0107 , James King , and Pat Morin . 2010. Odds-on trees. arXiv abs\/1002.1092 ( 2010 ). Prosenjit Bose, Luc Devroye, Karim Dou\u00efeb, Vida Dujmovi\u0107, James King, and Pat Morin. 2010. Odds-on trees. arXiv abs\/1002.1092 (2010)."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1240233.1240245"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/237218.237397"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02712873"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02712874"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798349188"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1721837.1721842"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/3116278.3116568"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009327"},{"key":"e_1_2_1_21_1","volume-title":"Proc. 31st Symposium on Computational Geometry.","author":"Timothy","unstructured":"Timothy M. Chan and Konstantinos Tsakalidas. 2015. Optimal deterministic algorithms for 2-d and 3-d shallow cuttings . In Proc. 31st Symposium on Computational Geometry. Timothy M. Chan and Konstantinos Tsakalidas. 2015. Optimal deterministic algorithms for 2-d and 3-d shallow cuttings. In Proc. 31st Symposium on Computational Geometry."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217026"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/120885.120892"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01377183"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01934990"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(94)00018-Q"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365723"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/201019.201036"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187740"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229163.2229173"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-002-0961-x"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03427-9"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/1496770.1496825"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00043-9"},{"key":"e_1_2_1_35_1","volume-title":"Proc. 11th ACM-SIAM Symposium on Discrete Algorithms. 743--752","author":"Demaine Erik D.","unstructured":"Erik D. Demaine , Alejandro L\u00f3pez-Ortiz , and J. Ian Munro . 2000. Adaptive set intersections, unions, and differences . In Proc. 11th ACM-SIAM Symposium on Discrete Algorithms. 743--752 . Erik D. Demaine, Alejandro L\u00f3pez-Ortiz, and J. Ian Munro. 2000. Adaptive set intersections, unions, and differences. In Proc. 11th ACM-SIAM Symposium on Discrete Algorithms. 743--752."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2014.03.011"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9440-y"},{"key":"e_1_2_1_38_1","volume-title":"Algorithms in Combinatorial Geometry","author":"Edelsbrunner Herbert","unstructured":"Herbert Edelsbrunner . 1987. Algorithms in Combinatorial Geometry . Springer-Verlag . Herbert Edelsbrunner. 1987. Algorithms in Combinatorial Geometry. Springer-Verlag."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220016"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/1037814.1037816"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00026-6"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/1496770.1496839"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.03.010"},{"key":"e_1_2_1_44_1","volume-title":"Computability and Complexity: From a Programming Perspective","author":"Jones Neil D.","unstructured":"Neil D. Jones . 1997. Computability and Complexity: From a Programming Perspective . MIT Press . Neil D. Jones. 1997. Computability and Complexity: From a Programming Perspective. MIT Press."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1077"},{"key":"e_1_2_1_46_1","volume-title":"Proc. 7th ACM-SIAM Symposium on Discrete Algorithms. 359--364","author":"Kenyon Claire","year":"1996","unstructured":"Claire Kenyon . 1996 . Best-fit bin-packing with random order . In Proc. 7th ACM-SIAM Symposium on Discrete Algorithms. 359--364 . Claire Kenyon. 1996. Best-fit bin-packing with random order. In Proc. 7th ACM-SIAM Symposium on Discrete Algorithms. 359--364."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212002"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/323233.323246"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215021"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02293051"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-044482537-7\/50014-0"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979018330X"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/4221.4259"},{"key":"e_1_2_1_54_1","volume-title":"Computational Geometry: An Introduction Through Randomized Algorithms","author":"Mulmuley Ketan","year":"1993","unstructured":"Ketan Mulmuley . 1993 . Computational Geometry: An Introduction Through Randomized Algorithms . Prentice Hall , Englewood Cliffs, NJ . Ketan Mulmuley. 1993. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, Englewood Cliffs, NJ."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1137\/0205001"},{"key":"e_1_2_1_56_1","volume-title":"Optimal Dominance Counting for a Non-Uniform Query Distribution in Linear Space","author":"Nguyen Cuong P.","unstructured":"Cuong P. Nguyen . 2015. Optimal Dominance Counting for a Non-Uniform Query Distribution in Linear Space . Dalhousie University . Bachelor of Computer Science Honours Thesis. Cuong P. Nguyen. 2015. Optimal Dominance Counting for a Non-Uniform Query Distribution in Linear Space. Dalhousie University. Bachelor of Computer Science Honours Thesis."},{"key":"e_1_2_1_57_1","volume-title":"Shamos","author":"Preparata Franco P.","year":"1985","unstructured":"Franco P. Preparata and Michael I . Shamos . 1985 . Computational Geometry : An Introduction. Springer-Verlag . Franco P. Preparata and Michael I. Shamos. 1985. Computational Geometry: An Introduction. Springer-Verlag."},{"key":"e_1_2_1_58_1","first-page":"194","article-title":"Distribution-sensitive algorithms","volume":"6","author":"Sen Sandeep","year":"1999","unstructured":"Sandeep Sen and Neelima Gupta . 1999 . Distribution-sensitive algorithms . Nordic Journal on Computing 6 (1999), 194 -- 211 . Sandeep Sen and Neelima Gupta. 1999. Distribution-sensitive algorithms. Nordic Journal on Computing 6 (1999), 194--211.","journal-title":"Nordic Journal on Computing"},{"key":"e_1_2_1_59_1","volume-title":"Handbook of Discrete and Computational Geometry, Jacob E. Goodman and Joseph O\u2019Rourke (Eds.)","author":"Snoeyink Jack","unstructured":"Jack Snoeyink . 1997. Point location . In Handbook of Discrete and Computational Geometry, Jacob E. Goodman and Joseph O\u2019Rourke (Eds.) . CRC Press , Boca Raton, FL , Chapter 30, 559--574. Jack Snoeyink. 1997. Point location. In Handbook of Discrete and Computational Geometry, Jacob E. Goodman and Joseph O\u2019Rourke (Eds.). CRC Press, Boca Raton, FL, Chapter 30, 559--574."},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990310"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523195"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/322276.322289"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220041"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218025"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3046673","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3046673","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:50:24Z","timestamp":1750218624000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3046673"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,2,28]]},"references-count":64,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,2,28]]}},"alternative-id":["10.1145\/3046673"],"URL":"https:\/\/doi.org\/10.1145\/3046673","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,2,28]]},"assertion":[{"value":"2015-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-03-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}