{"entities":{"Q3750120":{"pageid":5780026,"ns":120,"title":"Item:Q3750120","lastrevid":110589107,"modified":"2026-11-18T15:27:47Z","type":"item","id":"Q3750120","labels":{},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3986641"}},"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":"Q3750120$3572AD2D-B77E-4F9C-A9A5-14BF7531BD79","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d71505b7b39e0e5cc5840d37717d8ceee2acbde1","datavalue":{"value":"0609.68035","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3750120$C93FD7F9-F4B0-49A5-8745-2AA14F3FA9B5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9a4fe696494cc0e52acd419a922560dd99d2ce5a","datavalue":{"value":{"entity-type":"item","numeric-id":584276,"id":"Q584276"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3750120$84B9C094-C474-4BA2-BAFE-6FAA4ED190A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5ad91bd4a1378a015ef9d0cfb2ca621b16347f71","datavalue":{"value":{"entity-type":"item","numeric-id":525971,"id":"Q525971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3750120$3515919A-2F02-45D7-AAAE-FAE8136C94EF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q3750120$DEF5A64E-217A-46E5-AB5C-2A20065933AF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3750120$6D90C19B-B065-403A-976E-D2A6C8673DE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5ae9e2988e76d371f7e87b79bcd004ea2b80f64","datavalue":{"value":"51M20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3750120$FA9CA830-E293-4035-9081-5C6DDA7D5BEF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b5e01c36307741c5aba8e9240de68a444febb9b5","datavalue":{"value":"3986641","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3750120$BB2598DE-0E29-4F25-81FF-D9007F94C17A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a862f016acc1e519aa7b6644887bfca464692961","datavalue":{"value":"polynomial time","type":"string"},"datatype":"string"},"type":"statement","id":"Q3750120$A519BF23-A943-46ED-8866-26E5413BA242","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0a2529ffb094197ed1851cdc703b3e291c964c93","datavalue":{"value":"geometric complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q3750120$4F3838CC-80AE-4961-9431-9CF8E1B7492C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0f7f39d726f2105767649b6460de6344418ec962","datavalue":{"value":"decomposition of a simple polygon into a minimum number of convex polygons","type":"string"},"datatype":"string"},"type":"statement","id":"Q3750120$E106E732-9F7E-4C93-8321-EF8C310D3163","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bcbf8c2f587e60069a3d9240c5f0b0acffa92d02","datavalue":{"value":"optimal convex decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q3750120$E7E11502-60DB-464E-8AB8-300BCA285686","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e583c93d791f4d1f377aed0b1e49046826b2af34","datavalue":{"value":"Steiner points","type":"string"},"datatype":"string"},"type":"statement","id":"Q3750120$063F32B2-9016-4D86-892E-F17D5BDBB5B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0d82cfa81638332a8c825bcbbd9d7f7f9c0c45be","datavalue":{"value":"dynamic programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q3750120$DFC0BECB-268B-43A4-8979-097CB2B17532","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":"Q3750120$33E6D425-FE1C-471E-BFEF-2D3688DD3120","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"60e2f1015b125b364e971b9a6b2a3b6b66109b7c","datavalue":{"value":{"entity-type":"item","numeric-id":3358268,"id":"Q3358268"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"345afda6284a53edee8eacc3fdf6a5baca48d4a9","datavalue":{"value":{"amount":"+0.8532553911209106","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":"Q3750120$881EA674-B125-4FD3-889D-43DE3FC302A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc367938aca03938ab04474b6af3834287b9b43d","datavalue":{"value":{"entity-type":"item","numeric-id":4818554,"id":"Q4818554"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"85d5ed61061ff738d2cebe83cbd399273fe8abff","datavalue":{"value":{"amount":"+0.8388173580169678","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":"Q3750120$DC5A96C9-7E14-4B97-A890-5C30DCA4D614","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"361d4ece92e7f759031aca09ac481a6d43940865","datavalue":{"value":{"entity-type":"item","numeric-id":934018,"id":"Q934018"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"83f32e3f4f0f9d35bf3ebe61bdf4fb9d3ecf0d04","datavalue":{"value":{"amount":"+0.8373821377754211","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":"Q3750120$DF7C2BC7-C269-4717-B6A3-CD9732120F46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cb980103145fe027713c4bba4a3b4df5aec508e9","datavalue":{"value":{"entity-type":"item","numeric-id":1969864,"id":"Q1969864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d0e578116876a17bf30699897bfd12cd08a653f7","datavalue":{"value":{"amount":"+0.8373255729675293","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":"Q3750120$EDC790D8-E550-468F-B087-E7740F6F2251","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4288418071479d7d4ed5ae120eaff8e525ff7edb","datavalue":{"value":{"entity-type":"item","numeric-id":2507162,"id":"Q2507162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b51a906451f4794a7ea1ec665388d06c087b6b55","datavalue":{"value":{"amount":"+0.8288406133651733","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":"Q3750120$FEE56052-B693-44DD-A24E-1265C250F4FF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4a4ed2da9e6b7f77e1c70638b1d9f296ddcf206c","datavalue":{"value":"[For the entire collection see Zbl 0575.00022.] This contribution presents two algorithms for the decomposition of a simple polygon into a minimum number of convex polygons (the OCD problem \\(=\\) optimal convex decomposition). It is not without surprise that one makes the discovery that this problem is polynomial, and values this discovery accordingly. It is obvious that each vertex of a polygon displaying a reflex angle must be removed by the addition of a convex polygon to the decomposition, and at most two such vertices can be destroyed by this addition. The algorithms given by the authors circumvent the difficulty of having to introduce some interior Steiner points as vertices of the convex polygons generated, by considering particular patterns for which minimal decompositions can be generated, and which give the possibility of a dynamic programming approach. A basic \\(O(n^ 6)\\) algorithm is improved to an \\(O(n+c^ 3)\\) algorithm, where n is the number of vertices of the initial polygon, and c is the number of vertices which display a reflex angle.","type":"string"},"datatype":"string"},"type":"statement","id":"Q3750120$533CD168-6AB3-4C57-BAB6-C3AD17FCC35C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:3750120","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:3750120"}}}}}