{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T23:41:35Z","timestamp":1771026095900,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":50,"publisher":"ACM","license":[{"start":{"date-parts":[[2019,6,23]],"date-time":"2019-06-23T00:00:00Z","timestamp":1561248000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Nemzeti Kutat\u00e1si Fejleszt\u00e9si \u00e9s Innov\u00e1ci\u00f3s Hivatal","award":["K-116769,SNN-117879"],"award-info":[{"award-number":["K-116769,SNN-117879"]}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1452\/15"],"award-info":[{"award-number":["1452\/15"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","award":["200020-162884,200021-175977"],"award-info":[{"award-number":["200020-162884,200021-175977"]}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["678765"],"award-info":[{"award-number":["678765"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Magyar Tudom\u00e1nyos Akad\u00e9mia","award":["Lendulet Project in Cryptography"],"award-info":[{"award-number":["Lendulet Project in Cryptography"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2019,6,23]]},"DOI":"10.1145\/3313276.3316328","type":"proceedings-article","created":{"date-parts":[[2019,6,20]],"date-time":"2019-06-20T12:19:08Z","timestamp":1561033148000},"page":"1158-1166","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Planar point sets determine many pairwise crossing segments"],"prefix":"10.1145","author":[{"given":"J\u00e1nos","family":"Pach","sequence":"first","affiliation":[{"name":"EPFL, Switzerland \/ Renyi Institute, Hungary"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Natan","family":"Rubin","sequence":"additional","affiliation":[{"name":"Ben-Gurion University of the Negev, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"G\u00e1bor","family":"Tardos","sequence":"additional","affiliation":[{"name":"Renyi Institute, Hungary \/ Central European University, Hungary"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,6,23]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/3115960.3116064"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2006.08.002"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01196127"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1143176.1646569"},{"key":"e_1_3_2_1_5_1","unstructured":"O. Aichholzer personal communication. See http:\/\/www.eurogiga-compose.eu\/posezo.php  O. Aichholzer personal communication. See http:\/\/www.eurogiga-compose.eu\/posezo.php"},{"key":"e_1_3_2_1_6_1","first-page":"12","volume-title":"North-Holland","author":"Ajtai M.","year":"1982","unstructured":"M. Ajtai , V. Chv\u00e1tal , M. Newborn , E. Szemer\u00e9di , Crossing-free subgraphs. In : Theory and Practice of Combinatorics, North-Holland Mathematics Studies 60 , North-Holland , Amsterdam , 1982 , pp. 9\u00e2\u0102\u015e- 12 . M. Ajtai, V. Chv\u00e1tal, M. Newborn, E. Szemer\u00e9di, Crossing-free subgraphs. In: Theory and Practice of Combinatorics, North-Holland Mathematics Studies 60, North-Holland, Amsterdam, 1982, pp. 9\u00e2\u0102\u015e-12."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2004.12.008"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/109648.109687"},{"key":"e_1_3_2_1_9_1","volume-title":"Research Problems in Discrete Geometry","author":"Brass P.","year":"2005","unstructured":"P. Brass , W. Moser , and J. Pach : Research Problems in Discrete Geometry , Springer-Verlag , New York , 2005 . P. Brass, W. Moser, and J. Pach: Research Problems in Discrete Geometry, Springer-Verlag, New York, 2005."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-013-9538-5"},{"key":"e_1_3_2_1_11_1","first-page":"3","article-title":"Ramsey-type theorems for lines in 3-space","volume":"18","author":"Cardinal J.","year":"2016","unstructured":"J. Cardinal , M. S. Payne , and N. Solomon , Ramsey-type theorems for lines in 3-space , Discrete Math. Theor. Comput. Sci. 18 ( 2016 ), no. 3 , Paper No. 14, 16 pp. J. Cardinal, M. S. Payne, and N. Solomon, Ramsey-type theorems for lines in 3-space, Discrete Math. Theor. Comput. Sci. 18 (2016), no. 3, Paper No. 14, 16 pp.","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758854"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02189314"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02122778"},{"key":"e_1_3_2_1_15_1","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"2001","unstructured":"T. H. Cormen , C. E. Leiserson , R. L. Rivest , and C. Stein , Introduction to Algorithms , MIT Press , Cambridge, MA , 2001 . T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, MIT Press, Cambridge, MA, 2001."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009354"},{"key":"e_1_3_2_1_17_1","first-page":"4","article-title":"Incidence theorems and their applications","volume":"6","author":"Dvir Z.","year":"2010","unstructured":"Z. Dvir , Incidence theorems and their applications , Found. Trends Theor. Comput. Sci. 6 ( 2010 ), no. 4 , 257\u2013393 (2012). Z. Dvir, Incidence theorems and their applications, Found. Trends Theor. Comput. Sci. 6 (2010), no. 4, 257\u2013393 (2012).","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.4171\/JEMS\/705"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2008.06.002"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548309990459"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133123"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2012.03.011"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-018-0046-5"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/jdq087"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2010.05.015"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2015.181.1.2"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187876"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/2349130.2349133"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009357"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039834"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1994.1071"},{"key":"e_1_3_2_1_32_1","first-page":"1","article-title":"INDEPENDENT SET and CLIQUE problems in intersection-defined classes of graphs","volume":"31","author":"Kratochv\u00edl J.","year":"1990","unstructured":"J. Kratochv\u00edl and J. Ne\u0161et\u0159il , INDEPENDENT SET and CLIQUE problems in intersection-defined classes of graphs , Comment. Math. Univ. Carolin. 31 ( 1990 ), no. 1 , 85\u201393. J. Kratochv\u00edl and J. Ne\u0161et\u0159il, INDEPENDENT SET and CLIQUE problems in intersection-defined classes of graphs, Comment. Math. Univ. Carolin. 31 (1990), no. 1, 85\u201393.","journal-title":"Comment. Math. Univ. Carolin."},{"key":"e_1_3_2_1_33_1","first-page":"203","article-title":"On pairs of disjoint segments in convex position in the plane","volume":"20","author":"Kupitz Y.","year":"1984","unstructured":"Y. Kupitz , On pairs of disjoint segments in convex position in the plane , Ann. Discrete Math. 20 ( 1984 ), 203 \u2013 208 . Y. Kupitz, On pairs of disjoint segments in convex position in the plane, Ann. Discrete Math. 20 (1984), 203 \u2013 208.","journal-title":"Ann. Discrete Math."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2011.09.006"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1112\/blms\/26.2.132"},{"key":"e_1_3_2_1_36_1","series-title":"Foundations of Computing Series","volume-title":"Complexity Issues in VLSI","author":"Leighton T.","year":"1983","unstructured":"T. Leighton , Complexity Issues in VLSI , Foundations of Computing Series , MIT Press , Cambridge , 1983 . T. Leighton, Complexity Issues in VLSI, Foundations of Computing Series, MIT Press, Cambridge, 1983."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0039-7","volume-title":"Lectures on Discrete Geometry","author":"Matou\u0161ek J.","year":"2002","unstructured":"J. Matou\u0161ek , Lectures on Discrete Geometry , Springer-Verlag New York, Inc. , Secaucus, NJ , 2002 . J. Matou\u0161ek, Lectures on Discrete Geometry, Springer-Verlag New York, Inc., Secaucus, NJ, 2002."},{"key":"e_1_3_2_1_38_1","volume-title":"ACM Symposium on Computational Geometry","author":"Matou\u0161ek J.","year":"1991","unstructured":"J. Matou\u0161ek , Efficient partition trees, Discrete Comput. Geom. 8 (1992), no. 3, 315\u2013334. Also in: Proc . ACM Symposium on Computational Geometry ( North Conway, NH , 1991 ), 1\u20139. J. Matou\u0161ek, Efficient partition trees, Discrete Comput. Geom. 8 (1992), no. 3, 315\u2013334. Also in: Proc. ACM Symposium on Computational Geometry (North Conway, NH, 1991), 1\u20139."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1971.11992886"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2018.03.015"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548397003192"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2013.11.001"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-008-2250-z"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2017.02.006"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548397002976"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579194"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11083-015-9384-6"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01844852"},{"key":"e_1_3_2_1_49_1","volume-title":"The Mathematics of Paul Erd\u0151s, II. Algorithms Combin. 14","author":"Valtr P.","year":"1997","unstructured":"P. Valtr , On mutually avoiding sets , in: The Mathematics of Paul Erd\u0151s, II. Algorithms Combin. 14 , Springer , Berlin , 1997 , 324\u2013332. P. Valtr, On mutually avoiding sets, in: The Mathematics of Paul Erd\u0151s, II. Algorithms Combin. 14, Springer, Berlin, 1997, 324\u2013332."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009364"}],"event":{"name":"STOC '19: 51st Annual ACM SIGACT Symposium on the Theory of Computing","location":"Phoenix AZ USA","acronym":"STOC '19","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316328","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316328","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:01Z","timestamp":1750204441000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316328"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,23]]},"references-count":50,"alternative-id":["10.1145\/3313276.3316328","10.1145\/3313276"],"URL":"https:\/\/doi.org\/10.1145\/3313276.3316328","relation":{},"subject":[],"published":{"date-parts":[[2019,6,23]]},"assertion":[{"value":"2019-06-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}