{"entities":{"Q490307":{"pageid":492074,"ns":120,"title":"Item:Q490307","lastrevid":52177835,"modified":"2026-01-21T02:37:26Z","type":"item","id":"Q490307","labels":{"en":{"language":"en","value":"On computing the degree of convexity of polyominoes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6389246"}},"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":"Q490307$575386AF-84A6-44C0-B0B6-7EF4ACF71C25","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"84ecd6c94a5c4859f2f82e6f9dc915ce7bc07a08","datavalue":{"value":{"text":"On computing the degree of convexity of polyominoes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q490307$3407597D-6CDF-4366-95D2-06B6254E5FDD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a7d283842cf9f65c2f048eeb2419c1c54e4ba458","datavalue":{"value":"1305.05045","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q490307$628EB967-B44A-491D-8B86-6CEE71CF1C53","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b26467d1410b847c9ecdde038be52047c43c2066","datavalue":{"value":{"entity-type":"item","numeric-id":265060,"id":"Q265060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490307$2B221BD5-B3CF-4C02-BECC-27FEDF990AFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4b45831a6b64c2923a356b04498cc64a6cee6312","datavalue":{"value":{"entity-type":"item","numeric-id":490306,"id":"Q490306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490307$25D4CE39-359A-4E3B-B119-E6C1AD0B1EC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c7c631990d7449007f0f1f542693409be6081426","datavalue":{"value":{"entity-type":"item","numeric-id":288799,"id":"Q288799"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490307$A9BBC796-0BAC-4115-8D7C-CEF51D86DD93","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490307$15DB9936-C243-4DEF-AB63-7080EEC312CF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8bb6c16b18fb3fcb7c20a96f2fcd94ae71f0f929","datavalue":{"value":{"time":"+2015-01-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q490307$2018CCAB-40A0-4386-8836-D15BAC210CCB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5691be72831ca9b148f10e789377fe5fc0cba5d0","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p7","type":"string"},"datatype":"url"},"type":"statement","id":"Q490307$C2B9D3F9-4FD2-45C4-9E31-757AEBD9AA3F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e183e7f321cb5257bfdc8671bf2794bc83f6be1c","datavalue":{"value":"Summary: In this paper we present an algorithm which has as input a convex polyomino \\(P\\) and computes its degree of convexity, defined as the smallest integer \\(k\\) such that any two cells of \\(P\\) can be joined by a monotone path inside \\(P\\) with at most \\(k\\) changes of direction. The algorithm uses space \\(O(m + n)\\) to represent a polyomino \\(P\\) with \\(n\\) rows and \\(m\\) columns, and has a running time \\(O(\\min(m; r k))\\), where \\(r\\) is the number of corners of \\(P\\). Moreover, the algorithm leads naturally to a decomposition of \\(P\\) into simpler polyominoes.","type":"string"},"datatype":"string"},"type":"statement","id":"Q490307$F671673E-7B87-49F8-BA8F-166069F5BFCE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"44858eee6702c5fd32430c310ff496cbf7eec374","datavalue":{"value":"05B50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q490307$2D5CDC45-250A-4998-9C11-999051ADB956","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fa4669cf5eaa224b5d3554d9705827ca09f43afb","datavalue":{"value":"52A37","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q490307$4EE8D290-9B29-4FBC-822B-619D921F8891","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7ddaa80bf0a693a36c1113ff6b7ad576f729940","datavalue":{"value":"68W40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q490307$B67EFC10-B691-4828-9A07-48B27E1F8D88","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2cf773a3af3c94f4bdf98bd345c3ca69fbbb7fd4","datavalue":{"value":"6389246","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q490307$0098FFDF-29AD-4922-80F1-AB3C01271427","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5db9094e57c73b17a1d0e0247b8c207fa7ac692b","datavalue":{"value":"convex polyominoes","type":"string"},"datatype":"string"},"type":"statement","id":"Q490307$653D2418-53F2-43A2-B0AB-44D41AB2D85B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"89d1276e91a994636b4af468e33368579e20a4b8","datavalue":{"value":"degree of convexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q490307$E3C1C62A-0C0A-4B8C-8DC6-D26D98333290","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"f7893c5864b12fa090db965fa2550140fce2fc97","datavalue":{"value":{"entity-type":"item","numeric-id":15186,"id":"Q15186"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490307$FF2027C2-93E4-47CE-BB9B-3091920F207E","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":"Q490307$B8D77875-B7F3-4677-B670-8852DB17B2EB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0cb7c456c61fd4f2469ee3d5a859c64893a02b1e","datavalue":{"value":{"entity-type":"item","numeric-id":3651617,"id":"Q3651617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490307$94AAA5C0-D5E8-4F8B-8121-C4561B657982","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"288f71335183ea99c7ecca20bdea95a0dcf88639","datavalue":{"value":{"entity-type":"item","numeric-id":1918535,"id":"Q1918535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490307$76E08732-0CD2-46A1-B0B4-D20591C144AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5dfd17fe84575a8e5738cb07bd62609b04f4f039","datavalue":{"value":{"entity-type":"item","numeric-id":1939281,"id":"Q1939281"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490307$468C1388-1AAE-48DF-9E03-1F7183D9CC78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1611aa03f9504d68dfeb7f4be66849116fd43f08","datavalue":{"value":{"entity-type":"item","numeric-id":2372433,"id":"Q2372433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490307$801B8F20-5255-497C-9B10-D30075795014","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"831eab89d559e4616b72b82ba35f043f5bccce6b","datavalue":{"value":{"entity-type":"item","numeric-id":5316518,"id":"Q5316518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490307$F89CC5B0-9C48-41DA-B487-ACD73BFD96D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb58b79fe87c49f39ae1211531028e0728f83594","datavalue":{"value":{"entity-type":"item","numeric-id":3438927,"id":"Q3438927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490307$E3743D25-67D9-480C-8375-DFACC23FCF67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ffa27e9c9429616dfb34200c5714280968c610e8","datavalue":{"value":{"entity-type":"item","numeric-id":2490808,"id":"Q2490808"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490307$ADBAD02F-93D4-4E83-9AF8-580F0AC3D499","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4e46f31fba34a62e9b559bf37844cdbf9ae9c56","datavalue":{"value":{"entity-type":"item","numeric-id":1861555,"id":"Q1861555"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490307$9B119A61-0B03-424A-B2A5-E0B40C0C111F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f9875b140c1ff7af5b834defb64fca4e32b8c17","datavalue":{"value":{"entity-type":"item","numeric-id":1883680,"id":"Q1883680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490307$A4AD4725-0647-47D7-BE1A-7671F463E350","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0642debceda2905f287b21afe2a13ae05e6223c7","datavalue":{"value":{"entity-type":"item","numeric-id":1348529,"id":"Q1348529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490307$D6B6D83C-E14B-4AFC-97ED-2B1FA51B40A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1010d72993619afd4e068a229bce6ed70a05d11a","datavalue":{"value":{"entity-type":"item","numeric-id":2474263,"id":"Q2474263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490307$D9E26D46-75B3-494A-9082-9820AF71906D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c6858b5e08deae4b0167b3c57b8de8721528ffe5","datavalue":{"value":{"entity-type":"item","numeric-id":5829800,"id":"Q5829800"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490307$9E7411B6-4052-4C7C-89C3-330523A3F553","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"afa4e1ae54c568f4736daf2e9d2e57915c10504e","datavalue":{"value":{"entity-type":"item","numeric-id":2255820,"id":"Q2255820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490307$6D5B539C-8C12-4E76-B11F-0FB95C2E4046","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb0e35cb0b1e1d062873e8bac86342673f6b31ec","datavalue":{"value":{"entity-type":"item","numeric-id":396773,"id":"Q396773"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490307$AE85BA4F-CFB5-48A7-A2D9-1998B0D88D93","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"f5f7be613508d06c6ecfdb8ca62b6c4e46c206fb","datavalue":{"value":"bafkreicgtiegqaskfj6co2blk2z7fixqz3gvtnlasos72rnjgze4nqrk6u","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q490307$92FAD1A4-D6C2-4AFB-A00A-D6EB8227053A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"27264bcd582914f8fa29174ee140cec43d025a49","datavalue":{"value":{"entity-type":"item","numeric-id":517034,"id":"Q517034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c23a366e56382ccf6e795670b637c26063041d8a","datavalue":{"value":{"amount":"+0.889778733253479","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":"Q490307$6045A8E8-3905-4853-B56A-CE846E9829AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4acbcdd047bff6cfccba28eb4f66b56e2c915b1e","datavalue":{"value":{"entity-type":"item","numeric-id":1861555,"id":"Q1861555"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fed63b210a8fa0143ef44661758b05ed30254ce9","datavalue":{"value":{"amount":"+0.8086320757865906","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":"Q490307$68ED5195-8308-4366-8DB4-C3653D73D269","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"19ceb741f9233f2609ab5c0437b8f147d044829a","datavalue":{"value":{"entity-type":"item","numeric-id":3125664,"id":"Q3125664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fed63b210a8fa0143ef44661758b05ed30254ce9","datavalue":{"value":{"amount":"+0.8086320757865906","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":"Q490307$3FF09196-E184-49FA-8BC4-3D64A518544E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a3c37ee33c9ecf16cde39b5d77ee1bf21f261cde","datavalue":{"value":{"entity-type":"item","numeric-id":2255820,"id":"Q2255820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a270b8a918ae0453e939fd11ce9a0e8ae21afb4","datavalue":{"value":{"amount":"+0.7843072414398193","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":"Q490307$9B61B209-AE9C-484B-9594-00ACCE1E3E4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6a05628ccd22d8ae5ea193a3741455f111623c31","datavalue":{"value":{"entity-type":"item","numeric-id":1917521,"id":"Q1917521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"195779610a49bf4e03dcc0928cd0e1d778b37fd8","datavalue":{"value":{"amount":"+0.7842684388160706","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":"Q490307$D48031DA-99E8-4E86-BE9C-B9F8F364867B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:490307","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:490307"}}}}}