{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,29]],"date-time":"2025-12-29T13:50:45Z","timestamp":1767016245217,"version":"3.41.0"},"reference-count":87,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2015,11,2]],"date-time":"2015-11-02T00:00:00Z","timestamp":1446422400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF CAREER","award":["CCF-0746673"],"award-info":[{"award-number":["CCF-0746673"]}]},{"name":"US-Israel Binational Science Foundation"},{"name":"NSF","award":["CCF-1217338 and CNS-1318294"],"award-info":[{"award-number":["CCF-1217338 and CNS-1318294"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2015,11,2]]},"abstract":"<jats:p>\n            One of the longest-standing open problems in computational geometry is bounding the complexity of the lower envelope of\n            <jats:italic>n<\/jats:italic>\n            univariate functions, each pair of which crosses at most\n            <jats:italic>s<\/jats:italic>\n            times, for some fixed\n            <jats:italic>s<\/jats:italic>\n            . This problem is known to be equivalent to bounding the length of an order-\n            <jats:italic>s<\/jats:italic>\n            Davenport-Schinzel sequence, namely, a sequence over an\n            <jats:italic>n<\/jats:italic>\n            -letter alphabet that avoids alternating subsequences of the form\n            <jats:italic>a<\/jats:italic>\n            \u2026\n            <jats:italic>b<\/jats:italic>\n            \u2026\n            <jats:italic>a<\/jats:italic>\n            \u2026\n            <jats:italic>b<\/jats:italic>\n            \u2026 with length\n            <jats:italic>s<\/jats:italic>\n            +2. These sequences were introduced by Davenport and Schinzel in 1965 to model a certain problem in differential equations and have since been applied to bound the running times of geometric algorithms, data structures, and the combinatorial complexity of geometric arrangements.\n          <\/jats:p>\n          <jats:p>\n            Let \u03bb\n            <jats:sub>\n              <jats:italic>s<\/jats:italic>\n            <\/jats:sub>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) be the maximum length of an order-\n            <jats:italic>s<\/jats:italic>\n            DS sequence over\n            <jats:italic>n<\/jats:italic>\n            letters. What is \u03bb\n            <jats:sub>\n              <jats:italic>s<\/jats:italic>\n            <\/jats:sub>\n            asymptotically? This question has been answered satisfactorily [Hart and Sharir 1986; Agarwal et al. 1989; Klazar 1999; Nivasch 2010], when\n            <jats:italic>s<\/jats:italic>\n            is even or\n            <jats:italic>s<\/jats:italic>\n            \u2264 3. However, since the work of Agarwal et al. in the mid-1980s, there has been a persistent gap in our understanding of the odd orders.\n          <\/jats:p>\n          <jats:p>\n            In this work, we effectively close the problem by establishing sharp bounds on Davenport-Schinzel sequences of every order\n            <jats:italic>s<\/jats:italic>\n            . Our results reveal that, contrary to one's intuition, \u03bb\n            <jats:sub>\n              <jats:italic>s<\/jats:italic>\n            <\/jats:sub>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) behaves essentially like \u03bb\n            <jats:sub>\n              <jats:italic>s<\/jats:italic>\n              -1\n            <\/jats:sub>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) when\n            <jats:italic>s<\/jats:italic>\n            is odd. This refutes conjectures by Alon et al. [2008] and Nivasch [2010].\n          <\/jats:p>","DOI":"10.1145\/2794075","type":"journal-article","created":{"date-parts":[[2015,11,2]],"date-time":"2015-11-02T17:09:35Z","timestamp":1446484175000},"page":"1-40","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Sharp Bounds on Davenport-Schinzel Sequences of Every Order"],"prefix":"10.1145","volume":"62","author":[{"given":"Seth","family":"Pettie","sequence":"first","affiliation":[{"name":"University of Michigan, Ann Arbor, MI"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,11,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2009.01.008"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90677-8"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-002-0727-x"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(89)90032-0"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1435375.1435379"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195998000187"},{"volume-title":"Technical Report TR-71\/87. Institute of Computer Science","year":"1987","author":"Alon A.","key":"e_1_2_1_7_1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1455248.1455252"},{"volume-title":"Proceedings of the 5th International Workshop on Algorithms and Data Structures (WADS). 45--54","author":"Alstrup S.","key":"e_1_2_1_9_1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/98524.98575"},{"key":"e_1_2_1_11_1","first-page":"3","article-title":"Connect the dot: Computing feed-links for network extension","volume":"3","author":"Aronov B.","year":"2011","journal-title":"J. Spatial Inf. Sci."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-012-9422-8"},{"key":"e_1_2_1_13_1","unstructured":"B. Aronov and D. Drusvyatskiy. 2011. Complexity of a single face in an arrangement of s-intersecting curves. CoRR abs\/1108.4336 (2011).  B. Aronov and D. Drusvyatskiy. 2011. Complexity of a single face in an arrangement of s -intersecting curves. CoRR abs\/1108.4336 (2011)."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0898-1221(85)90105-1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2009.10.002"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11786-012-0111-z"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2012.01.012"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/42282.214094"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"M. W. Bern D. Eppstein P. E. Plassman and F. F. Yao. 1991. Horizon theorems for lines and polygons. In Discrete and Computational Geometry: Papers from the DIMACS Special Year Jacob E. Goodman Richard Pollack and William Steiger (Eds.). Number 6 in DIMACS Ser. Discrete Math. and Theoretical Computer Science. Amer. Math. Soc. 45--66.  M. W. Bern D. Eppstein P. E. Plassman and F. F. Yao. 1991. Horizon theorems for lines and polygons. In Discrete and Computational Geometry: Papers from the DIMACS Special Year Jacob E. Goodman Richard Pollack and William Steiger (Eds.). Number 6 in DIMACS Ser. Discrete Math. and Theoretical Computer Science. Amer. Math. Soc. 45--66.","DOI":"10.1090\/dimacs\/006\/03"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1177\/02783640122068173"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.1029"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/355541.355562"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195991000049"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2012.04.004"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(89)80003-3"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"H. Davenport. 1970\/1971. A combinatorial problem connected with differential equations. II. Acta Arith. 17 (1970\/1971) 363--372.  H. Davenport. 1970\/1971. A combinatorial problem connected with differential equations. II. Acta Arith. 17 (1970\/1971) 363--372.","DOI":"10.4064\/aa-17-4-363-372"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.2307\/2373068"},{"key":"e_1_2_1_28_1","first-page":"63","article-title":"A note on sequences and subsequences","volume":"20","author":"Davenport H.","year":"1965","journal-title":"Elemente Der Mathematik"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1810959.1810968"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.03.046"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2009.03.008"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1987.44"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702407515"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1998196.1998199"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/110858586"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2008.02.040"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90316-8"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.3"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2009.03.004"},{"volume":"570","volume-title":"Proceedings of the 17th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'91)","author":"Guibas L. J.","key":"e_1_2_1_40_1"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799362627"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579170"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/98524.98599"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90204-9"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02189323"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2004.09.018"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/73393.73430"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2010.11.001"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(92)90005-W"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1137\/0403009"},{"key":"e_1_2_1_51_1","first-page":"737","article-title":"A general upper bound in extremal theory of sequences","volume":"33","author":"Klazar M.","year":"1992","journal-title":"Comment. Math. Univ. Carolin."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/049\/11"},{"key":"e_1_2_1_53_1","first-page":"A11","article-title":"Generalized Davenport-Schinzel sequences: Results, problems, and applications","volume":"2","author":"Klazar M.","year":"2002","journal-title":"Integers"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01302967"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1017460.1017461"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702408387"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(88)90055-6"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/357062.357071"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187883"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.21471"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2004.04.002"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979018330X"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2006.11.001"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/1706591.1706597"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-006-0014-1"},{"volume-title":"Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms (SODA). 1115--1124","year":"2008","author":"Pettie S.","key":"e_1_2_1_66_1"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873719"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2011.06.020"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2011.02.011"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/1998196.1998258"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1137\/080735862"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722169"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579209"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02122559"},{"key":"e_1_2_1_75_1","unstructured":"M. Sharir and P. Agarwal. 1995. Davenport-Schinzel Sequences and their Geometric Applications. Cambridge University Press.   M. Sharir and P. Agarwal. 1995. Davenport-Schinzel Sequences and their Geometric Applications. Cambridge University Press."},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1986.23"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(94)90011-6"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25878-7_26"},{"key":"e_1_2_1_79_1","doi-asserted-by":"crossref","unstructured":"E. Szemer\u00e9di. 1973\/74. On a problem of Davenport and Schinzel. Acta Arith. 25 (1973\/74) 213--224.  E. Szemer\u00e9di. 1973\/74. On a problem of Davenport and Schinzel. Acta Arith. 25 (1973\/74) 213--224.","DOI":"10.4064\/aa-25-2-213-224"},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02712877"},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2004.11.015"},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1145\/321879.321884"},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1145\/322154.322161"},{"volume-title":"Proceedings of the 5th International Symposium on Graph Drawing (GD)","series-title":"Lecture Notes in Computer Science","author":"Valtr P.","key":"e_1_2_1_84_1"},{"volume-title":"Proceedings of the 13th International Conference on Computer and Information Technology (ICCIT). 325--330","author":"Wahid M. A.","key":"e_1_2_1_85_1"},{"key":"e_1_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187894"},{"key":"e_1_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802185"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2794075","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2794075","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:04:26Z","timestamp":1750273466000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2794075"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,11,2]]},"references-count":87,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2015,11,2]]}},"alternative-id":["10.1145\/2794075"],"URL":"https:\/\/doi.org\/10.1145\/2794075","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2015,11,2]]},"assertion":[{"value":"2012-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-11-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}