{"entities":{"Q1263970":{"pageid":1274720,"ns":120,"title":"Item:Q1263970","lastrevid":68333442,"modified":"2026-04-12T23:00:01Z","type":"item","id":"Q1263970","labels":{"en":{"language":"en","value":"Approximation algorithms for partitioning a rectangle with interior points"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4128381"}},"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":"Q1263970$0F25A652-5909-45F4-8ED6-4A3C672A2107","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e0ae85461039d7d70fadf0bae8f4674ef6b15dce","datavalue":{"value":{"text":"Approximation algorithms for partitioning a rectangle with interior points","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1263970$99FDEF39-764B-4FB2-8878-FC0CA610EE4A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"75d20634296698377f02d87d556ab9c845dbae77","datavalue":{"value":"0688.68035","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1263970$8C54CBFF-17DE-4523-8BBE-0E5318AE5CAE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2ff6fd06c99c490dd507f1d6c47d84259b534964","datavalue":{"value":"10.1007/BF01840375","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1263970$22157220-0740-4FB3-A6E8-9C05A720F1CF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b0fdab848737bdf10c9fff60c8aca4346ad8e904","datavalue":{"value":{"entity-type":"item","numeric-id":1123612,"id":"Q1123612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1263970$B516091E-ECC4-4011-BCA7-27934521AB38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"dc11152e79285b1105c94eee7fb922884a1cabd0","datavalue":{"value":{"entity-type":"item","numeric-id":293372,"id":"Q293372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1263970$B9B9E9DA-C872-4F10-8916-DE086E9E5000","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1263970$120DE84E-942A-4C23-854E-C838DE42363E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1263970$0D72EE70-6D58-4281-A7F9-712A3AC0BCC0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"bc38faa7ec3c88a0a3c14f79fc985583125b8b31","datavalue":{"value":"The article addresses the problem of partitioning a rectilinear polygon into rectangles by introducing a set of line segments (edges) of least total length. Several variations of this problem were shown to be NP- hard, but the computational complexity of some related problems remains unknown. Particularly, the authors present an efficient approximation algorithm for the case where a set of points inside rectilinear polygon is also given and a valid partition must not contain points from this set. The solutions generated by the algorithm are guaranteed to be within three times the optimal solution value. The method used is transformation of a given instance into an instance of another variation of the problem, which we know to solve in polynomial time. It is shown that this approach guarantees abovementioned bounds of approximation.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1263970$CD6527FB-F02C-4B77-9B7A-B427F066F5F3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1263970$C606736E-F944-45C6-BA81-04F9C75BCA3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ddd8cb1932c6bc41681458db5f685a2a286fde55","datavalue":{"value":"52Bxx","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1263970$8A922176-50A9-41C6-8FF0-741C8D1FAC20","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d7412bbe3355ff9227a6b01631ed7659bc74c693","datavalue":{"value":"4128381","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1263970$12E4D536-5321-43B5-A7B4-601C2E74EFA6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc4837877785b4675d8ac1c6d4c911bcaf794e13","datavalue":{"value":"approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1263970$8C90D9E6-D667-41A8-B912-6818159F7531","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d767af8baa65dfef14c04213ecedb2bcc65e2286","datavalue":{"value":"partition of rectilinear polygons","type":"string"},"datatype":"string"},"type":"statement","id":"Q1263970$169EE35E-DE07-4019-8C0E-F2BD6378826F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e90b7870184b4fec8c274946c1560c81ece1d150","datavalue":{"value":"polynomial time complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1263970$C98142C2-4DA8-4589-A5E6-A72F46296ECA","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4418b7d4f2a0250db5c25bb23e561efd56a43eb7","datavalue":{"value":{"entity-type":"item","numeric-id":587571,"id":"Q587571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1263970$30F743CB-2941-4B4E-AB0E-01FA31E6F968","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":"Q1263970$4BFD3EF0-0393-4F11-A95D-376294C83580","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"340ea97c0f2f383d364057042ebc9f9438fcc85a","datavalue":{"value":{"entity-type":"item","numeric-id":4091421,"id":"Q4091421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1263970$69EB754A-0209-4AB8-8094-B68D6629BD67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ae0713540eb691df7bd8820bc004fcb597f484c","datavalue":{"value":{"entity-type":"item","numeric-id":1249042,"id":"Q1249042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1263970$E2F4DE23-C7F5-4EFD-A2F1-FDB9581E76C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f7cb17f07afc81b882a02b9298b806a3a61347e1","datavalue":{"value":{"entity-type":"item","numeric-id":3962480,"id":"Q3962480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1263970$7CC8070F-10FB-4090-A00A-718A893CD70D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d93af916faa5c843c45840c214061db86a0a99fa","datavalue":{"value":{"entity-type":"item","numeric-id":3854665,"id":"Q3854665"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1263970$40295DB8-1128-4131-9680-10DC355521BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a096a8834d112e39b5e1d115c74ef31c6a120aab","datavalue":{"value":{"entity-type":"item","numeric-id":3893361,"id":"Q3893361"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1263970$DE160350-F0F1-4A51-B065-55ED2838F5C4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"81eb55de8a99292e63276fb439f73b1662518cc8","datavalue":{"value":"https://doi.org/10.1007/bf01840375","type":"string"},"datatype":"url"},"type":"statement","id":"Q1263970$948C9FD4-3892-4ADC-BA29-29CF9DDF9993","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ef40ac610d41b8bc99f33b792cb619129cf5fbe1","datavalue":{"value":"W2032846908","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1263970$59DC0491-FAC5-4E27-9FEC-3B98E08E5997","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"297497f1b6c357507aed699a7be0b1d9116c6efe","datavalue":{"value":{"entity-type":"item","numeric-id":5404455,"id":"Q5404455"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d98590001a3feb6fbcee19725d516e2e256c50e5","datavalue":{"value":{"amount":"+0.9146257","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":"Q1263970$D7AE1C67-30E0-415C-8636-84858B1DDDDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ca13337e7f4cd231e4638b2d162c47280af42292","datavalue":{"value":{"entity-type":"item","numeric-id":869574,"id":"Q869574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2253d89fc84cfd5ec2f7ae5a6500d272d7bd40df","datavalue":{"value":{"amount":"+0.9070258","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":"Q1263970$56195735-1BA2-40D3-A2C5-3AAB7EA769C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"30492eebae081a40280ac9602dcd60aaff215a12","datavalue":{"value":{"entity-type":"item","numeric-id":5191656,"id":"Q5191656"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2253d89fc84cfd5ec2f7ae5a6500d272d7bd40df","datavalue":{"value":{"amount":"+0.9070258","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":"Q1263970$D9A84DBD-7709-4F23-928C-CB27F8E4117B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"17d3484f96a2c22cf8590f40a6989819c2532b43","datavalue":{"value":{"entity-type":"item","numeric-id":3796749,"id":"Q3796749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"741422340dc72e656dfc888ce2ce587833b5c12d","datavalue":{"value":{"amount":"+0.9068873","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":"Q1263970$9C201F50-F0B9-41DE-983E-1DEEAEB32F42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cc156c37bd6939130d3abe6a53ff0a2f5e2b7e7d","datavalue":{"value":{"entity-type":"item","numeric-id":1849374,"id":"Q1849374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"95845a83deafec86164473d81028fd7845b212ac","datavalue":{"value":{"amount":"+0.90585864","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":"Q1263970$CF83DA00-FAD3-4ABE-A924-065EF900DE6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7321354932cbf792d551a84ef0bc14e61287f120","datavalue":{"value":{"entity-type":"item","numeric-id":3786288,"id":"Q3786288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"af0b3a8a8d6ee373ab1f56938537a6daf86b90db","datavalue":{"value":{"amount":"+0.8998243","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":"Q1263970$45BEFA13-81F7-4C6D-AE07-9F4C51CAB5E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aeb45bb52a7f19d7243d47c5dea82517f37090a5","datavalue":{"value":{"entity-type":"item","numeric-id":1102107,"id":"Q1102107"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5fd8b41d7215e025853db49c571ec784ef3424b6","datavalue":{"value":{"amount":"+0.8947502","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":"Q1263970$05C738BA-3C6B-4AF5-BF8B-03B52D81CDD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b3462a8b94281f7f4953d68c45ba27fb3abb6af","datavalue":{"value":{"entity-type":"item","numeric-id":1882473,"id":"Q1882473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4736317066d84ad98f3c06625391e83a204fe2bb","datavalue":{"value":{"amount":"+0.8896185","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":"Q1263970$BE2B5BAF-7007-4BB0-B20D-4A82F7500C9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7768d9ee76ac3803eafc032964d0cd06e08a9801","datavalue":{"value":{"entity-type":"item","numeric-id":5363011,"id":"Q5363011"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bad0b3b7f1101bc59a96ab57c50a401efd3448fd","datavalue":{"value":{"amount":"+0.8864692","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":"Q1263970$42D2A3DC-9B24-4422-AFDB-5203CEE2FD7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1599431a6b3e9e582faef5233a7eca9fa26487fd","datavalue":{"value":{"entity-type":"item","numeric-id":912618,"id":"Q912618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e38b81118b842064135ff93443ea061d17e7b612","datavalue":{"value":{"amount":"+0.883764","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":"Q1263970$6BEC4DF2-8901-4C85-91EB-813FC30CFD84","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Approximation algorithms for partitioning a rectangle with interior points","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Approximation_algorithms_for_partitioning_a_rectangle_with_interior_points"}}}}}