{"entities":{"Q1853137":{"pageid":1863879,"ns":120,"title":"Item:Q1853137","lastrevid":71501253,"modified":"2026-04-13T22:40:55Z","type":"item","id":"Q1853137","labels":{"en":{"language":"en","value":"Binary space partitions for axis-parallel line segments: Size-height tradeoffs."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1856476"}},"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":"Q1853137$AEA4AD17-64E9-468E-9BCA-357CBAF1E522","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"733f12c482dcf62956c4ed325fae6bf656b19163","datavalue":{"value":{"text":"Binary space partitions for axis-parallel line segments: Size-height tradeoffs.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1853137$8F1DCBC9-FFAC-4525-B2B2-72CC5400463C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2d082ca47145490b34edc57a2672c61a9d7d11b1","datavalue":{"value":"1042.68107","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853137$5E9CECC6-273D-4D42-9784-A146214BA467","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"756ec3078ecc01914e8cfd26f94eeffc010a84ab","datavalue":{"value":"10.1016/S0020-0190(02)00284-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853137$DDD45A59-6F08-402E-84E1-C06646A56947","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bd8b7aa5abc28b023a6525a716374e0834612669","datavalue":{"value":{"entity-type":"item","numeric-id":293202,"id":"Q293202"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853137$8077111E-B586-42EB-9C28-B23A4F49BEDF","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":"Q1853137$D1CCACEF-429F-41B2-AABC-F0CE501014A9","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":"Q1853137$9718246B-0A6C-4CF6-9719-532B75AEF91E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9b4be9fa24095ef9a951c08ca991a68b6d6f8e76","datavalue":{"value":"We present worst-case lower bounds on the minimum size of a Binary Space Partition (BSP) tree as a function of its height, for a set \\(S\\) of \\(n\\) axis-parallel line segments in the plane. We assume that the BSP uses only axis-parallel cutting lines. These lower bounds imply that, in the worst case, a BSP tree of height \\(O(\\log n)\\) must have size \\(\\Omega(n\\log n)\\) and a BSP tree of size \\(O(n)\\) must have height \\(\\Omega(n^{\\delta})\\), where \\(\\delta\\) is a suitable constant.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853137$3B322897-D21C-405D-AFA0-85B2B71362A1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853137$632934A9-123D-4FDE-9BC2-0E7C06C8A719","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7e0caf35dc059858f192f18f2aaeb3004fc33c6b","datavalue":{"value":"1856476","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853137$365D69B2-E85F-4234-B021-1C1BF9B7B067","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0032d5eb6e50d1531a77194b8aacf827853e28","datavalue":{"value":"Computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853137$EC9C43FF-F63B-41B8-A997-9963BA51EE25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d26fd6f43dbfcef447ab112eab54cfee70c89870","datavalue":{"value":"Binary space partitions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853137$053DCE8F-F594-40C6-9F30-6885033A6B69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"530d182f681c6fda97fd677281e2daf4ae60fc0b","datavalue":{"value":"Line segments","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853137$16923272-E02A-46B6-A77A-D339BFCB4B88","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":"Q1853137$D262FB2B-D152-4EEC-86AF-B9A3A0F49AFB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"440ba0d9dbee427a1b508f6b771488e2dd84f87d","datavalue":{"value":{"entity-type":"item","numeric-id":4369857,"id":"Q4369857"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853137$41941C57-BDBC-4016-BD1C-B9633D10C68A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"59b07b272905adefb46ff9cd30e39f9e61d3bb8c","datavalue":{"value":{"entity-type":"item","numeric-id":1209352,"id":"Q1209352"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853137$B72FD02A-FB54-46D7-AB05-24FD1B81E520","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5de8ad7e905bdd01ee76c23dee94c798c8ddabc4","datavalue":{"value":{"entity-type":"item","numeric-id":1370930,"id":"Q1370930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853137$7A4CEBD0-E015-43AF-B2DD-85771428C4E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"22fcb1fc5b4b58e340af8d5b8bb94ef4e4939398","datavalue":{"value":{"entity-type":"item","numeric-id":5361570,"id":"Q5361570"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853137$AB1DCAB6-C854-4266-96C7-C8C140F88D2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc6482fda869c7df0ed32fd6ade8f790a1ff04cc","datavalue":{"value":{"entity-type":"item","numeric-id":5585020,"id":"Q5585020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853137$3CD64DBE-438D-4A7A-9D78-308C6E43CB09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f27b27cbbfacd5de84a7949e1d56cfad571684cb","datavalue":{"value":{"entity-type":"item","numeric-id":914380,"id":"Q914380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853137$3EB6A8D5-4F9B-448E-A8B5-5349DF30BDD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed0a5b9bf80fc36528630c90e29c066f70340ee4","datavalue":{"value":{"entity-type":"item","numeric-id":3990617,"id":"Q3990617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853137$DF9F837E-C579-425E-8139-8DD6C7F7CFC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3605246a2b50c346da4d4bf9d7f08d9eac8fc89","datavalue":{"value":{"entity-type":"item","numeric-id":5361571,"id":"Q5361571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853137$9998927C-6910-480E-8EF3-DC33224EEDF2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"bdf42c4656ede09b4e5a93b702f980324f36d92a","datavalue":{"value":"https://doi.org/10.1016/s0020-0190(02)00284-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q1853137$8FD46190-9456-4ED4-B3A9-E7A5EFF737BF","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c7500a6b10f0203b042cf06434e1acf9ab88315f","datavalue":{"value":"W2149634922","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853137$B0110E19-24E8-4549-8D4F-ECAB93F3AAA9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1dd1ffb385495dc6ffb3f5d9f76fa4b615ebcb16","datavalue":{"value":{"entity-type":"item","numeric-id":5361570,"id":"Q5361570"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e3c3e1ea3a4520aec17756cbd3b564bc9436d379","datavalue":{"value":{"amount":"+0.9125713","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":"Q1853137$B6BB2362-80B7-4A91-BC2F-583D24A41E49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"22d290f0a1385c12defa94596ef3ed0b2180ed05","datavalue":{"value":{"entity-type":"item","numeric-id":1880211,"id":"Q1880211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e3c3e1ea3a4520aec17756cbd3b564bc9436d379","datavalue":{"value":{"amount":"+0.9125713","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":"Q1853137$394B37FE-1C05-4D8B-845C-6B8C3290D99B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c9152a6845e2422bdd3bdedae465403fe01f4672","datavalue":{"value":{"entity-type":"item","numeric-id":4828969,"id":"Q4828969"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fdaadbb39187cc6538f81bc6c73d3cae35563fd6","datavalue":{"value":{"amount":"+0.89783776","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":"Q1853137$E0C3F47D-8DBC-4557-A87D-38B18800C539","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6a1c4cb439d8ff525bbea67c62d083f44a17e14f","datavalue":{"value":{"entity-type":"item","numeric-id":4706194,"id":"Q4706194"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fdaadbb39187cc6538f81bc6c73d3cae35563fd6","datavalue":{"value":{"amount":"+0.89783776","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":"Q1853137$D4904284-268A-4B17-91A9-C7A574FBEB2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a17d8fb48befa8c9e2c03e6a93b173c740bd6efe","datavalue":{"value":{"entity-type":"item","numeric-id":3614166,"id":"Q3614166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e0724ceab4606081672104111b7e1057fa9121a4","datavalue":{"value":{"amount":"+0.87607896","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":"Q1853137$081CF874-258C-4524-9A5A-5F39A6E469C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"620d6c7b77ccc23d78b474c1d7a370ace2f21f7d","datavalue":{"value":{"entity-type":"item","numeric-id":5299997,"id":"Q5299997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"887b1c46511082898292decf175839f4faad186e","datavalue":{"value":{"amount":"+0.8675857","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":"Q1853137$249F3FB3-6657-4666-8E9A-8E628AC9BF39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fd237b023274bb1d9467809c2f6cb5a218f4371a","datavalue":{"value":{"entity-type":"item","numeric-id":1587784,"id":"Q1587784"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8b93a3925504b668216f1f520e49635481e2eb7b","datavalue":{"value":{"amount":"+0.86728317","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":"Q1853137$46B89501-6806-40B0-B735-FA05EF74FCCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"99449b62465a03ee38b1261bc07422433c34b564","datavalue":{"value":{"entity-type":"item","numeric-id":3990617,"id":"Q3990617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d04a0b2daf27fc22b8f2bb204d75f788a58bbda3","datavalue":{"value":{"amount":"+0.8595283","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":"Q1853137$5EA1A999-FED5-4C52-A902-1029F6481669","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"34b3972472b72a58b5eda81c6f42b233affa4fc8","datavalue":{"value":{"entity-type":"item","numeric-id":4943877,"id":"Q4943877"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"58694c6fe6c9014ed134924defe413491a6dbff0","datavalue":{"value":{"amount":"+0.8517125","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":"Q1853137$F1AC40CF-6E66-415F-A279-E73A06B7D576","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"04dbd57f0e8a1eaeb23cf448ad0d6fc77fb5dc47","datavalue":{"value":{"entity-type":"item","numeric-id":5897271,"id":"Q5897271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b46591d3a047af84ee672ee7a2934a34101677ae","datavalue":{"value":{"amount":"+0.84771746","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":"Q1853137$B7371C8E-9566-461B-A4AA-6E5EF494F753","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Binary space partitions for axis-parallel line segments: Size-height tradeoffs.","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Binary_space_partitions_for_axis-parallel_line_segments:_Size-height_tradeoffs."}}}}}