{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:46:10Z","timestamp":1740109570728,"version":"3.37.3"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,1,22]],"date-time":"2022-01-22T00:00:00Z","timestamp":1642809600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,1,22]],"date-time":"2022-01-22T00:00:00Z","timestamp":1642809600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["FE 340\/11-1"],"award-info":[{"award-number":["FE 340\/11-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["J-3847-N35"],"award-info":[{"award-number":["J-3847-N35"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2022,3]]},"abstract":"Abstract<\/jats:title>We consider arrangements ofn<\/jats:italic>pseudo-lines in the Euclidean plane where each pseudo-line$$\\ell _i$$<\/jats:tex-math>\u2113<\/mml:mi>i<\/mml:mi><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula>is represented by a bi-infinite connectedx<\/jats:italic>-monotone curve$$f_i(x)$$<\/jats:tex-math>f<\/mml:mi>i<\/mml:mi><\/mml:msub>(<\/mml:mo>x<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>,$$x \\in \\mathbb {R}$$<\/jats:tex-math>x<\/mml:mi>\u2208<\/mml:mo>R<\/mml:mi><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, such that for any two pseudo-lines$$\\ell _i$$<\/jats:tex-math>\u2113<\/mml:mi>i<\/mml:mi><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula>and$$\\ell _j$$<\/jats:tex-math>\u2113<\/mml:mi>j<\/mml:mi><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula>with$$i \\!<\\! j$$<\/jats:tex-math>i<\/mml:mi><<\/mml:mo>j<\/mml:mi><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, the function$$x \\!\\mapsto \\! f_j(x) \\!-\\! f_i(x)$$<\/jats:tex-math>x<\/mml:mi>\u21a6<\/mml:mo>f<\/mml:mi>j<\/mml:mi><\/mml:msub>(<\/mml:mo>x<\/mml:mi>)<\/mml:mo><\/mml:mrow>-<\/mml:mo>f<\/mml:mi>i<\/mml:mi><\/mml:msub>(<\/mml:mo>x<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>is monotonically decreasing and surjective (i.e., the pseudo-lines approach each other until they cross, and then move away from each other). We show that sucharrangements of approaching pseudo-lines<\/jats:italic>, under some aspects, behave similar to arrangements of lines, while for other aspects, they share the freedom of general pseudo-line arrangements. For the former, we prove:There are arrangements of pseudo-lines that are not realizable with approaching pseudo-lines.<\/jats:p><\/jats:list-item>Every arrangement of approaching pseudo-lines has a dual generalized configuration of points with an underlying arrangement of approaching pseudo-lines.<\/jats:p><\/jats:list-item><\/jats:list>For the latter, we show:There are$$2^{\\Theta (n^2)}$$<\/jats:tex-math>2<\/mml:mn>\u0398<\/mml:mi>(<\/mml:mo>n<\/mml:mi>2<\/mml:mn><\/mml:msup>)<\/mml:mo><\/mml:mrow><\/mml:msup><\/mml:math><\/jats:alternatives><\/jats:inline-formula>isomorphism classes of arrangements of approaching pseudo-lines (while there are only$$2^{\\Theta (n \\log n)}$$<\/jats:tex-math>2<\/mml:mn>\u0398<\/mml:mi>(<\/mml:mo>n<\/mml:mi>log<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:msup><\/mml:math><\/jats:alternatives><\/jats:inline-formula>isomorphism classes of line arrangements).<\/jats:p><\/jats:list-item>It can be decided in polynomial time whether an allowable sequence is realizable by an arrangement of approaching pseudo-lines.<\/jats:p><\/jats:list-item><\/jats:list>Furthermore, arrangements of approaching pseudo-lines can be transformed into each other by flipping triangular cells, i.e., they have a connected flip graph, and every bichromatic arrangement of this type contains a bichromatic triangular cell.<\/jats:p>","DOI":"10.1007\/s00454-021-00361-w","type":"journal-article","created":{"date-parts":[[2022,1,24]],"date-time":"2022-01-24T11:03:16Z","timestamp":1643022196000},"page":"380-402","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Arrangements of Approaching Pseudo-Lines"],"prefix":"10.1007","volume":"67","author":[{"given":"Stefan","family":"Felsner","sequence":"first","affiliation":[]},{"given":"Alexander","family":"Pilz","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2172-9285","authenticated-orcid":false,"given":"Patrick","family":"Schnider","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,1,22]]},"reference":[{"issue":"1","key":"361_CR1","doi-asserted-by":"publisher","first-page":"87","DOI":"10.7155\/jgaa.00350","volume":"19","author":"O Aichholzer","year":"2015","unstructured":"Aichholzer, O., Hackl, T., Lutteropp, S., Mchedlidze, T., Pilz, A., Vogtenhuber, B.: Monotone simultaneous embeddings of upward planar digraphs. J. Graph Algorithms Appl. 19(1), 87\u2013110 (2015)","journal-title":"J. Graph Algorithms Appl."},{"key":"361_CR2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-44205-0","volume-title":"Proofs from THE BOOK","author":"M Aigner","year":"2014","unstructured":"Aigner, M., Ziegler, G.M.: Proofs from THE BOOK. Springer, Berlin (2014)"},{"issue":"20","key":"361_CR3","doi-asserted-by":"publisher","first-page":"4745","DOI":"10.1016\/j.disc.2007.08.086","volume":"308","author":"A Asinowski","year":"2008","unstructured":"Asinowski, A.: Suballowable sequences and geometric permutations. Discret. Math. 308(20), 4745\u20134762 (2008)","journal-title":"Discret. Math."},{"key":"361_CR4","volume-title":"Oriented Matroids. Encyclopedia of Mathematics and its Applications","author":"A Bj\u00f6rner","year":"1993","unstructured":"Bj\u00f6rner, A., Las Vergnas, M., Sturmfels, B., White, N., Ziegler, G.M.: Oriented Matroids. Encyclopedia of Mathematics and its Applications, vol. 46. Cambridge University Press, Cambridge (1993)"},{"issue":"2","key":"361_CR5","doi-asserted-by":"publisher","first-page":"211","DOI":"10.7155\/jgaa.00319","volume":"18","author":"D Eppstein","year":"2014","unstructured":"Eppstein, D.: Drawing arrangement graphs in small grids, or how to play planarity. J. Graph Algorithms Appl. 18(2), 211\u2013231 (2014)","journal-title":"J. Graph Algorithms Appl."},{"key":"361_CR6","unstructured":"Eppstein, D., van Garderen, M., Speckmann, B., Ueckerdt, T.: Convex-arc drawings of pseudolines (2016). arXiv:1601.06865"},{"issue":"3","key":"361_CR7","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1007\/PL00009471","volume":"22","author":"S Felsner","year":"1999","unstructured":"Felsner, S., Kriegel, K.: Triangles in Euclidean arrangements. Discret. Comput. Geom. 22(3), 429\u2013438 (1999)","journal-title":"Discret. Comput. Geom."},{"issue":"1","key":"361_CR8","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/0012-365X(80)90096-5","volume":"32","author":"JE Goodman","year":"1980","unstructured":"Goodman, J.E.: Proof of a conjecture of Burr, Gr\u00fcnbaum, and Sloane. Discret. Math. 32(1), 27\u201335 (1980)","journal-title":"Discret. Math."},{"key":"361_CR9","doi-asserted-by":"crossref","unstructured":"Goodman, J.E., Pollack, R.: Helly-type theorems for pseudoline arrangements in P$$^2$$. J. Comb. Theory Ser. A 32(1), 1\u201319 (1982)","DOI":"10.1016\/0097-3165(82)90061-9"},{"issue":"3","key":"361_CR10","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/0097-3165(84)90050-5","volume":"37","author":"JE Goodman","year":"1984","unstructured":"Goodman, J.E., Pollack, R.: Semispaces of configurations, cell complexes of arrangements. J. Comb. Theory Ser. A 37(3), 257\u2013293 (1984)","journal-title":"J. Comb. Theory Ser. A"},{"issue":"6","key":"361_CR11","doi-asserted-by":"publisher","first-page":"725","DOI":"10.1002\/cpa.3160380606","volume":"38","author":"JE Goodman","year":"1985","unstructured":"Goodman, J.E., Pollack, R.: Polynomial realization of pseudoline arrangements. Commun. Pure Appl. Math. 38(6), 725\u2013732 (1985)","journal-title":"Commun. Pure Appl. Math."},{"issue":"3","key":"361_CR12","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/BF02187696","volume":"1","author":"JE Goodman","year":"1986","unstructured":"Goodman, J.E., Pollack, R.: Upper bounds for configurations and polytopes in $${\\varvec { R}}^d$$. Discret. Comput. Geom. 1(3), 219\u2013227 (1986)","journal-title":"Discret. Comput. Geom."},{"issue":"9","key":"361_CR13","doi-asserted-by":"publisher","first-page":"866","DOI":"10.1080\/00029890.1994.11997040","volume":"101","author":"JE Goodman","year":"1994","unstructured":"Goodman, J.E., Pollack, R., Wenger, R., Zamfirescu, T.: Arrangements and topological planes. Am. Math. Monthly 101(9), 866\u2013878 (1994)","journal-title":"Am. Math. Monthly"},{"issue":"3","key":"361_CR14","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/BF01212978","volume":"14","author":"JE Goodman","year":"1994","unstructured":"Goodman, J.E., Pollack, R., Wenger, R., Zamfirescu, T.: Every arrangement extends to a spread. Combinatorica 14(3), 301\u2013306 (1994)","journal-title":"Combinatorica"},{"key":"361_CR15","unstructured":"Hoffmann, U.: Intersection Graphs and Geometric Objects in the Plane. PhD thesis, Technische Universit\u00e4t Berlin (2016)"},{"key":"361_CR16","volume-title":"Vector Calculus","author":"JE Marsden","year":"1996","unstructured":"Marsden, J.E., Trompa, A.J.: Vector Calculus. W.H. Freeman, New York (1996)"},{"key":"361_CR17","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0039-7","volume-title":"Lectures on Discrete Geometry. Graduate Texts in Mathematics","author":"J Matou\u0161ek","year":"2002","unstructured":"Matou\u0161ek, J.: Lectures on Discrete Geometry. Graduate Texts in Mathematics, vol. 212. Springer, New York (2002)"},{"key":"361_CR18","doi-asserted-by":"crossref","unstructured":"Mn\u00ebv, N.E.: The universality theorems on the classification problem of configuration varieties and convex polytopes varieties. In: Topology and Geometry\u2014Rohlin Seminar. Lecture Notes in Math., vol. 1346, pp. 527\u2013543. Springer, Berlin (1988)","DOI":"10.1007\/BFb0082792"},{"key":"361_CR19","unstructured":"Pilz, A., Welzl, E., Wettstein, M.: From crossing-free graphs on wheel sets to embracing simplices and polytopes with few vertices. In: 33rd International Symposium on Computational Geometry (Brisbane 2017). Leibniz Int. Proc. Inform., vol. 77, #\u00a054. Leibniz-Zent. Inform., Wadern (2017)"},{"key":"361_CR20","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/BF01166556","volume":"64","author":"G Ringel","year":"1956","unstructured":"Ringel, G.: Teilungen der Ebene durch Geraden oder topologische Geraden. Math. Z. 64, 79\u2013102 (1956)","journal-title":"Math. Z."},{"issue":"4","key":"361_CR21","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1016\/S0195-6698(84)80039-6","volume":"5","author":"RP Stanley","year":"1984","unstructured":"Stanley, R.P.: On the number of reduced decompositions of elements of Coxeter groups. Eur. J. Comb. 5(4), 359\u2013372 (1984)","journal-title":"Eur. J. Comb."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-021-00361-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-021-00361-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-021-00361-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,24]],"date-time":"2023-01-24T10:18:14Z","timestamp":1674555494000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-021-00361-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,22]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["361"],"URL":"https:\/\/doi.org\/10.1007\/s00454-021-00361-w","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2022,1,22]]},"assertion":[{"value":"22 January 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 September 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 September 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 January 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}