{"entities":{"Q1853175":{"pageid":1863917,"ns":120,"title":"Item:Q1853175","lastrevid":71501568,"modified":"2026-04-13T22:41:01Z","type":"item","id":"Q1853175","labels":{"en":{"language":"en","value":"Transversal of disjoint convex polygons."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1856505"}},"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":"Q1853175$640214B9-9FB4-4114-97CB-44DD677B88BA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"153458ccfa1007cf6e92cee6f87f474b2910161c","datavalue":{"value":{"text":"Transversal of disjoint convex polygons.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1853175$940C8A46-A1FD-4B15-8190-99BDD83BC74C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"928bc399576968ec5bd101247f5bb7f6df09529a","datavalue":{"value":"1042.68109","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853175$0AB750F4-1324-4894-9245-0982941DFA08","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e2ec80840604c7f78c8644a37f3259a6a1444906","datavalue":{"value":"10.1016/S0020-0190(02)00414-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853175$DF69CA22-415A-4DF4-BB98-3EA76C6E248F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ca27f7bdaa490e761f9f7c24443656b33b69930e","datavalue":{"value":{"entity-type":"item","numeric-id":328688,"id":"Q328688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853175$9FD8AE28-E635-44C2-B79B-148F1639F2AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e2f28a915bfb06f8371d14f34b4419f16ab7f955","datavalue":{"value":{"entity-type":"item","numeric-id":182320,"id":"Q182320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853175$56232637-D382-4736-9BE4-D0497BAFFD5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"672cfd3116ece8b46bc4472502e2c4ecc06299c0","datavalue":{"value":{"entity-type":"item","numeric-id":1853054,"id":"Q1853054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853175$634F2AC6-5C27-410F-820A-F92EC1F6AD40","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853175$39C40196-CC16-4366-B691-F564BCB2EAC9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5b5e42af6f5e314fbfeffbcec47ae99c9eed44fd","datavalue":{"value":{"time":"+2003-01-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1853175$4454A580-46D4-496D-A24F-9310B191ED54","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"bd0bcf626edd3389c78785d8070e28f3fe01e691","datavalue":{"value":"Given a set \\(S\\) of \\(n\\) disjoint convex polygons \\({P_{i}\\mid1<i<n}\\) in a plane, each with \\(k_{i}\\) vertices, the transversal problem is to find, if there exists one, a straight line that goes through every polygon in \\(S.\\) We show that the transversal problem can be solved in \\(O(N+n\\log n)\\) time, where \\(N=\\sum_{i=1}^{n}k_{i}\\) is the total number of vertices of the polygons.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853175$BD82C5AA-47E0-4FD9-BD3D-D299FEA25D4F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853175$BC0C18D5-9799-449C-8B85-60A1E7EE6AAF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"010c41c43aaaf88af164a499f8245494df3dae8a","datavalue":{"value":"1856505","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853175$89978D70-B4A9-473B-A8E8-8CD12E6CC38A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0032d5eb6e50d1531a77194b8aacf827853e28","datavalue":{"value":"Computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853175$3A1DACF0-730A-47AC-8802-4FA6FF7A3ADA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1e826f69792d804763e92c24c7207d679dcb8f21","datavalue":{"value":"Transversal","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853175$1C7671AF-9EFD-4962-83F6-3B48A73F0CE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6843cde191c9ee947cbd3cbb94181ad67d03e0f0","datavalue":{"value":"Disjoint convex polygon","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853175$E0D6438F-D6C8-402D-9D45-483D7E78B91A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1ec5ef5d76d7a3b1701ab37bbe620708224b3811","datavalue":{"value":"Stabber","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853175$C37D2575-B080-404D-853D-3AA56CB95D21","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":"Q1853175$3BF2E3C2-0DBC-409A-8BE0-AF0CB429917E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7665c1640a9da2eb8d01a5539680d51d13fa3a15","datavalue":{"value":{"entity-type":"item","numeric-id":3315272,"id":"Q3315272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853175$A77C2A7A-6BA9-4B7D-AD7F-BECD659F01CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"887c863fb1e5886d8bd55e0ef38b8e2220f95123","datavalue":{"value":{"entity-type":"item","numeric-id":1083215,"id":"Q1083215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853175$F04E38E0-0026-4EEA-A34F-E53FC8F1834A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"94d87a027c696d4cca9cf462e499936419e44e67","datavalue":{"value":{"entity-type":"item","numeric-id":1163869,"id":"Q1163869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853175$B660220F-67EC-429E-A9C8-35644E33C9C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a9e941b224ae72629b3e2cd083153eeebdfa379","datavalue":{"value":{"entity-type":"item","numeric-id":3670553,"id":"Q3670553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853175$6A98500F-8A2F-4C33-9148-C36D8C47DA27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f837c623bf58c21b7997511c468a133c0deb27a9","datavalue":{"value":{"entity-type":"item","numeric-id":3778541,"id":"Q3778541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853175$59841979-8A15-44AA-A9C7-2B9AE0979C30","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee75a6d3003a4f703955601dac25f21aac1f02e3","datavalue":{"value":{"entity-type":"item","numeric-id":1853055,"id":"Q1853055"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f52c295b405dcad83f81dcc140ded2627646a6af","datavalue":{"value":{"amount":"+0.89058566","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1853175$25379041-3876-40F3-BF9F-3994BF530619","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b62053f28f5bc33c85b553f1638899e3413fae66","datavalue":{"value":{"entity-type":"item","numeric-id":2812150,"id":"Q2812150"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b53b154359908063372fcfac28a0ab33e773562","datavalue":{"value":{"amount":"+0.88782877","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1853175$A943B80B-16F4-47EA-B6C5-998B78BD48F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"47da1eed7c4ddd5659bf201bb88fa111dfb9dedf","datavalue":{"value":{"entity-type":"item","numeric-id":5870601,"id":"Q5870601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"91e9ac22d096ec6cc65c63b710b474fa18a21e91","datavalue":{"value":{"amount":"+0.8611827","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1853175$9A188CC9-391A-44C0-A176-FB15F8E4A37E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"50651310466826fc2cd3df8a5c2c0f5271d94810","datavalue":{"value":{"entity-type":"item","numeric-id":5488369,"id":"Q5488369"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"af34f3e56b665d677f04e31f0737bd342a874608","datavalue":{"value":{"amount":"+0.86001635","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1853175$AA4E5216-D412-4A99-AB8C-060C97C61512","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6351baeca70bd5348b33cc97bd1e1331466c4964","datavalue":{"value":{"entity-type":"item","numeric-id":3562855,"id":"Q3562855"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f1bb2c6349e60a564399c68658194c0774392473","datavalue":{"value":{"amount":"+0.85766435","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1853175$C0DCFB8B-0A16-44CA-A661-34DCE89F317C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"48bbdeb378f1320c9da13e4ba197b2bb1077e905","datavalue":{"value":{"entity-type":"item","numeric-id":2529037,"id":"Q2529037"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eee24a62247df133589e6d49123eca0dc13bec70","datavalue":{"value":{"amount":"+0.8555102","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1853175$BB07F4A1-189E-43E6-88DC-F652DB5EA6A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d609be617b8cf260f50339cfb2767f2853bcecd3","datavalue":{"value":{"entity-type":"item","numeric-id":1005918,"id":"Q1005918"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0e1154c14f41cc2516c1c05f45e9415b29c7d7ff","datavalue":{"value":{"amount":"+0.8549852","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1853175$E6D7A4A9-3802-4C55-9149-F94DA2EAB029","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0bf41227d559396c537a44e802865629541cec74","datavalue":{"value":{"entity-type":"item","numeric-id":4649945,"id":"Q4649945"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d97fb078e13aeae3095afab21570d7be78aad568","datavalue":{"value":{"amount":"+0.854203","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1853175$2601D7AE-99B7-4B70-9CE7-071118C1092C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b04b66e143a389152775f92050d6b94e46809444","datavalue":{"value":{"entity-type":"item","numeric-id":3449827,"id":"Q3449827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a43f4a0e5861e102c2891277569bbfa7f2920a13","datavalue":{"value":{"amount":"+0.85320127","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1853175$6C76822A-9B98-4917-878A-42F375817ACF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"17a8be39ba29e6115decc3ba98f868a7a1a67ff2","datavalue":{"value":{"entity-type":"item","numeric-id":5366966,"id":"Q5366966"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a43f4a0e5861e102c2891277569bbfa7f2920a13","datavalue":{"value":{"amount":"+0.85320127","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1853175$C76309AD-A902-49D3-B6F2-7D90D0DF340C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Transversal of disjoint convex polygons.","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Transversal_of_disjoint_convex_polygons."}}}}}