{"entities":{"Q1869746":{"pageid":1880488,"ns":120,"title":"Item:Q1869746","lastrevid":69059616,"modified":"2026-04-13T04:16:09Z","type":"item","id":"Q1869746","labels":{"en":{"language":"en","value":"Monotone paths in line arrangements"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1902835"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1869746$6C16A548-7978-486F-8EAF-B47213867700","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a3210deba9a737838023c652ba26a8cb280e38bf","datavalue":{"value":{"text":"Monotone paths in line arrangements","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1869746$8CC27AEC-0CF4-447C-90F0-45B7C9A5E1E6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"06d9f51d12fd3021d251e20be33b2cca235c56bb","datavalue":{"value":"1042.52021","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1869746$10F79B76-32CB-4EA8-9195-9D37C6C09AEA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"aaec44852b7b85a6a26f63276d712bbd5784dbdf","datavalue":{"value":"10.1016/S0925-7721(02)00136-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1869746$1D460EF3-369F-40FB-B45A-43D04EB48433","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a96f81364fc2855d011471bf136b17cad7e460e2","datavalue":{"value":{"entity-type":"item","numeric-id":405216,"id":"Q405216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1869746$D655102F-A229-403D-840A-89A3F00930FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f1dc5e40d7a8a3386725a84b223a56083987b2ef","datavalue":{"value":{"entity-type":"item","numeric-id":178539,"id":"Q178539"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1869746$6BC7D61C-4687-4746-86F0-07888FC4DE77","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"285beb29e5e30a7ba8792191178d7f52682884ef","datavalue":{"value":{"entity-type":"item","numeric-id":175378,"id":"Q175378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1869746$9C604BE7-483A-43B9-9546-BF7F520809FD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3b05751a28df8b7d171e02c18dec5082d33efa41","datavalue":{"value":{"time":"+2003-04-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1869746$2CBF13CB-E75D-4208-8C41-C0B1FD7D64C7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8cf880fd54dcba2eda78eec43fe74fd70ce6621a","datavalue":{"value":"The \\(k\\)-level of a line arrangement is an x-monotone path on the lines of the arrangement which turns in every intersection, and there are exactly \\(k\\) lines which pass below each point of this path. Its length is the number of turns plus one. The \\(k\\)-level problem for arrangements asks for the length of the longest x-monotone path in an arrangement with \\(n\\) lines (the best known upper bound is \\(O(nk^{\\frac{1}{3}})\\) [\\textit{T. K. Dey}, Discrete Comput. Geom. 19, 373--382 (1998; Zbl 0899.68107)] and the best known lower bound is \\(ne^{\\Omega(\\sqrt{\\log(k)})}\\) [\\textit{G. T\u00f3th}, Discrete Comput. Geom. 26, 187--194 (2001; Zbl 0988.52028)] for \\(n \\leq 2k\\)).  In this paper, the authors consider the following generalization of this problem: Find the maximal length of an x-monotone path on an arrangement of \\(n\\) lines (without the condition that the path has to do a turn on each intersection). The best known result for a lower bound (\\(\\Omega(n^{5/3})\\)) is due to \\textit{J. Matou\u0161ek} [Discrete Comput. Geom. 6, 385--406 (1991; Zbl 0765.68210)]. The main result of this paper is a better lower bound: \\(\\Omega(n^{7/4})\\). The authors achieve this result by constructing arrangements of \\(n\\) lines (which consists of some subsets of parallel lines) with x-monotone path of length \\(\\Omega(n^{7/4})\\). At the end, they also improve a bit the trivial upper bound \\({n \\choose 2}+1\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1869746$345A974D-F74D-4D83-9D24-41FF9FD03AFC","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"8f31b35cc2a3770c9505a0612f451c75af31238e","datavalue":{"value":{"entity-type":"item","numeric-id":405225,"id":"Q405225"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1869746$F0ED55D2-F17A-4200-B40B-58086165C922","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2762df744fec88c5da60f696833f02907bd4417a","datavalue":{"value":"52B55","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1869746$DA2B4082-84F1-49EB-97CA-7CEABC8BD7E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"af5af707ed729d722feccff88208277cb39cbff7","datavalue":{"value":"52C30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1869746$2BE2B4FA-C67C-4EE7-A411-79AC5E94A012","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1869746$2AB34194-2367-4DE5-966C-12CC2A063D13","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"97c34b1a7b1fb72ece3c72ba4c1e09ad3bfa71ad","datavalue":{"value":"1902835","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1869746$E0C60A51-4863-4D62-B76B-97349BFEE369","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a5770b1ed2851a3799695af7284075ed4f2b2f1","datavalue":{"value":"line arrangement","type":"string"},"datatype":"string"},"type":"statement","id":"Q1869746$9D23DAF0-231E-4CF2-BF72-603DDD1EE546","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"70277998ea2f6d2dc60df48f7d4ed3065749543b","datavalue":{"value":"monotone path","type":"string"},"datatype":"string"},"type":"statement","id":"Q1869746$980A9384-738B-485A-BF91-F04988E4B39D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2d69626348db86c4a250dfef87f3904c148d1a5e","datavalue":{"value":"\\(k\\)-level","type":"string"},"datatype":"string"},"type":"statement","id":"Q1869746$B84EF754-EBAD-47C7-856C-2FFF930CF22E","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1869746$1EB01812-CE60-48E7-A193-DA1D18688C7B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e74a55fe8a1084c81cdca259fb6715fe51a1720a","datavalue":{"value":{"entity-type":"item","numeric-id":1387847,"id":"Q1387847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1869746$FE2B98BD-5D36-406F-A620-0287533F6CFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25b026e498c7466f890693e678f90760ff4b1c4e","datavalue":{"value":{"entity-type":"item","numeric-id":3772828,"id":"Q3772828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1869746$DEE9C7E4-0518-466D-9B5F-E7D6A7E7DE24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d51e66379b70ceed54487a727ee6745d725b0e35","datavalue":{"value":{"entity-type":"item","numeric-id":1122981,"id":"Q1122981"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1869746$E35C6D05-9C93-45F5-98DE-E5637B90ADD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f51c8be2264b52a98bdcc805e45a587c836e7995","datavalue":{"value":{"entity-type":"item","numeric-id":276089,"id":"Q276089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1869746$0E9BB8AD-2824-4002-A602-6DC35DD6E315","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f008ff6ef8ff17ba2dc931dfc3da0de1a1cc1976","datavalue":{"value":{"entity-type":"item","numeric-id":4339095,"id":"Q4339095"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1869746$3BDD51ED-52B0-413F-9D2A-5C4F3608C01C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"64693cac22fcc5ff56e88c4c53cbfeef7516fcd3","datavalue":{"value":{"entity-type":"item","numeric-id":5946377,"id":"Q5946377"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1869746$3A4D0C78-5242-495B-ABE3-50AC25E2BD49","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a31a7cbaf54a3496d0c0047f276e46a81eddf150","datavalue":{"value":"https://doi.org/10.1016/s0925-7721(02)00136-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q1869746$E238A862-2431-4064-A511-C42E984BEDEE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c3d6ad484e5e68af738c4d7f2ff176d63c2694ce","datavalue":{"value":"W2212856239","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1869746$ACE5FD8C-9C0B-459F-B40C-DB46AF28157A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7a8c01ec0efd572fe30e35c3d95f13d0d356e316","datavalue":{"value":{"entity-type":"item","numeric-id":1762943,"id":"Q1762943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"81b03ae7cbc00a951757d099de6e39000429babe","datavalue":{"value":{"amount":"+0.8962746262550354","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1869746$CFBFC02C-C78F-484C-AD06-0AB100452F00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f650da03c4192326265bbd0ab6e7fcee8fdfe1ec","datavalue":{"value":{"entity-type":"item","numeric-id":5361614,"id":"Q5361614"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"91ec90b1f8aa44ac91decca194d52ac5cc664e7d","datavalue":{"value":{"amount":"+0.8950216174125671","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1869746$A284BB71-DAC4-4B7C-9DFE-6675BF60644C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9c2fba006d7325ae2927933107406fde9f7a5b26","datavalue":{"value":{"entity-type":"item","numeric-id":276089,"id":"Q276089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d7f546a0e44358c889341448b5cb064c530bbc57","datavalue":{"value":{"amount":"+0.8904094099998474","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1869746$0FEE8BCE-CFAC-41FA-B991-6E71632BE1E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4d8377fd7fa400ccc51375c74432434cdcf43f07","datavalue":{"value":{"entity-type":"item","numeric-id":2387201,"id":"Q2387201"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d7af30f44b62c8604a0929e4c451b0eb96c72080","datavalue":{"value":{"amount":"+0.8894726037979126","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1869746$1D45F36F-22D7-4F67-BBAE-41284E45C86B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bdeaa72006628a2775bb40c2f0f869460f40179b","datavalue":{"value":{"entity-type":"item","numeric-id":2484004,"id":"Q2484004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9fab1e5bbc408dc3c4a6425293c0f71c36cb7cd2","datavalue":{"value":{"amount":"+0.8766888976097107","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1869746$584A1F27-198B-4A4B-B7A5-A04C62E5CB45","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Monotone paths in line arrangements","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Monotone_paths_in_line_arrangements"}}}}}