{"entities":{"Q1102107":{"pageid":1112859,"ns":120,"title":"Item:Q1102107","lastrevid":69955224,"modified":"2026-04-13T11:28:09Z","type":"item","id":"Q1102107","labels":{"en":{"language":"en","value":"Algorithms for minimum length partitions of polygons"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4049040"}},"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":"Q1102107$04BC0F29-B2EF-4433-8178-8DE6CA3CBCE6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"73aeb279cb4ae247a2d23c8aa2a99f5fcc74cffe","datavalue":{"value":{"text":"Algorithms for minimum length partitions of polygons","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1102107$40DE8D10-080B-4263-9EB4-248E6EDA6293","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"126de6f316ee896b1339c91f77b4afa95d37a9e3","datavalue":{"value":"0643.68047","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102107$C2601862-E2B6-4A63-A9BD-229FAD9413B4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"87dc6d3cfc612f94536e9b89e10944cf4adbad4b","datavalue":{"value":"10.1007/BF01937272","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102107$DA6B9940-8AE7-4814-9DB1-3168A4CF7D68","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"00dfebb11dde3a8ec3e20741cb39008a3351335c","datavalue":{"value":{"entity-type":"item","numeric-id":293198,"id":"Q293198"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102107$DE4F01EB-BBB1-4B9E-A187-5EFCF00445D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d0dc835d004d9da5bffbf23ad19f48702adc4590","datavalue":{"value":{"entity-type":"item","numeric-id":582112,"id":"Q582112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102107$F63EB830-93C9-4323-AC6A-DB68D0C5058E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ca02099175697a4b54d6c3e10f20112dbf6ee98b","datavalue":{"value":{"entity-type":"item","numeric-id":170449,"id":"Q170449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102107$88BC1D54-B5F6-497D-AB50-D7106CF9CD21","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e560271c921b84b65a9b7f0d3fa6830623f8af8b","datavalue":{"value":{"entity-type":"item","numeric-id":188629,"id":"Q188629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102107$94AE55F0-AD7F-4178-9BBC-F9BC81265F34","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-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":"Q1102107$FFE92ADD-445D-4560-A739-8CA297F3228E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"847b80186a14759fc8613294121938468281f263","datavalue":{"value":"We show that it is possible to find a diagonal partition of any n-vertex simple polygon into smaller polygons, each of at most m edges, minimizing the total length of the partitioning diagonals, in time \\(O(n^ 3 m^ 2)\\). We derive the same asymptotic upper time-bound for minimum length diagonal partitions of simple polygons into exactly m-gons provided that the input polgyon can be partitioned into m-gons. Also, in the latter case, if the input polygon is convex, we can reduce the upper time-bound to \\(O(n^ 3 \\log m)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1102107$3CCF0BF7-1921-425F-B4F3-BDA978E618DD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102107$AE2212E2-6AD9-4EA4-AEA0-9BB0791761F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"25fe30a6fe5285f54b3a7ea7d7e97ac0b640e4f9","datavalue":{"value":"68R99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102107$E9517C03-2477-4AFB-A844-9B1F04D0ECB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4e1df7ba929664ba7b91d5a816f05411516abc3","datavalue":{"value":"52C17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102107$A2A5BAA4-0F53-4F6A-B851-903BBA0485BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb6fa31c061028a10fb1c2a1679af7746583c504","datavalue":{"value":"05B40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102107$9787E563-9F50-49E9-8258-A217856E09B4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c2cda80e064abc0c4bfc7049c3c57df2747e1074","datavalue":{"value":"4049040","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102107$2E33EA59-8C6A-4700-8D47-7DD22E6ED35F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a1445a326f12be49cc61d5afaae314c2399f7615","datavalue":{"value":"geometric partition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1102107$3FD34F57-8EB0-47A0-A39A-410224881FD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1102107$B9C28D67-22A6-4ABA-A20F-60AB5D3C18DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2c4df5c0cd246319ec98364cc18f750639d6c6e1","datavalue":{"value":"VLSI","type":"string"},"datatype":"string"},"type":"statement","id":"Q1102107$A05BAC7D-83AF-41E5-8F10-FA5D448335D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ed28385b5c62eaaf3b0756eb74715fae1afa8293","datavalue":{"value":"simple polygon","type":"string"},"datatype":"string"},"type":"statement","id":"Q1102107$A3D240B5-7D62-4F73-9A50-3E7A4DC9E445","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":"Q1102107$CA36081E-34AB-45C9-ADED-56B2686484B4","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"253a8870cc5482fe2a6163cdac37c8bb5961aaf0","datavalue":{"value":"Q62037529","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102107$15EB6EE9-DC57-497E-A004-47728C74DD0F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"91d0f5ab233e414c684abbb389e5f82d2ca7af57","datavalue":{"value":{"entity-type":"item","numeric-id":3911413,"id":"Q3911413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102107$420A7A4A-6CBE-4722-969B-0A16BC731A16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ebfb063389676a32c32c9a9730fa309059ea3a51","datavalue":{"value":{"entity-type":"item","numeric-id":4094387,"id":"Q4094387"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102107$F970D109-A6CF-4983-BE13-8C965C769A35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b7ee5780baed1d7856c99389fada17672a0a4e3","datavalue":{"value":{"entity-type":"item","numeric-id":3898497,"id":"Q3898497"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102107$48E02DA0-0B3A-4CDA-B8D6-7ACBFD19E930","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"74caa8dd26dc163a670e2aae9e70cc7322d01346","datavalue":{"value":{"entity-type":"item","numeric-id":3315016,"id":"Q3315016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102107$3D39E035-667D-43B1-A955-A0D431B0D28A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b4e573f6b223942ce0b2f64be67dd67446285343","datavalue":{"value":{"entity-type":"item","numeric-id":1069709,"id":"Q1069709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102107$507FA011-BEC6-4C25-819C-97102BB229CF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"84a7a56b67490c6ba28dd72443f25c047aaaf0e1","datavalue":{"value":"https://doi.org/10.1007/bf01937272","type":"string"},"datatype":"url"},"type":"statement","id":"Q1102107$E02537E7-89B2-4EC3-9A4D-FCA20DD0F0AE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7f51cea20d815f48e13c3d04d0e317d08895bc14","datavalue":{"value":"W1966745172","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102107$BE052BCD-B0CD-4DCC-8590-C592AC90E4C9","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"ad136a4394b1801c79fb55b6476081e2c1c0a419","datavalue":{"value":"journals/bit/LingasLS87","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102107$31B9EE45-86D7-4C72-A735-0D336EBD1BDB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1a5c81f91346af4c33579516b72f47bfcb21ffa4","datavalue":{"value":{"entity-type":"item","numeric-id":3217601,"id":"Q3217601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"15d199406face6e06b8233742a107507175a908f","datavalue":{"value":{"amount":"+0.8613675236701965","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":"Q1102107$F5E4D3D0-9E06-4AEB-9378-F1ADA4C0760B","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":"e5b467f740459e4a8a89c17bf9417ae21010de9a","datavalue":{"value":{"amount":"+0.8168640732765198","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":"Q1102107$87EC55B6-0C3E-46B9-9E80-0EB5A2F27BB3","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":"3293c7f84d8ae3a02170653fc31ab639344547a0","datavalue":{"value":{"amount":"+0.8127889633178711","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":"Q1102107$A6E6C208-6540-4A37-A2F1-B7B7245FA03D","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":"45e2594d04bf29510a7e6b3360c0825b604bafc7","datavalue":{"value":{"amount":"+0.8108493685722351","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":"Q1102107$8FF9CF2C-3871-4B6D-97B3-121C2A988433","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"47584999b3579b24028f8eb32c33cadf324354b5","datavalue":{"value":{"entity-type":"item","numeric-id":808305,"id":"Q808305"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"60b878ff85cb2bc7ed254f060c248c607f251fe2","datavalue":{"value":{"amount":"+0.8017470240592957","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":"Q1102107$9E94A58E-C0E5-450F-9A48-667989BF1552","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Algorithms for minimum length partitions of polygons","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Algorithms_for_minimum_length_partitions_of_polygons"}}}}}