{"entities":{"Q811138":{"pageid":812986,"ns":120,"title":"Item:Q811138","lastrevid":49552120,"modified":"2026-01-07T17:13:37Z","type":"item","id":"Q811138","labels":{"en":{"language":"en","value":"NP-harte Probleme f\u00fcr minimale Polygon\u00fcberdeckungen. (NP-hard problems for minimal polygon coverings)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4215404"}},"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":"Q811138$A0BB4348-ED96-4823-AE0C-3A6E80C1BB64","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"91acee8bed9740fb463ea8af4200a48c21d39cbd","datavalue":{"value":{"text":"NP-harte Probleme f\u00fcr minimale Polygon\u00fcberdeckungen. (NP-hard problems for minimal polygon coverings)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q811138$39B6E089-5910-465D-A015-3CADAAF2D0C4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0f4288745e5fef06e3d1d83129a72842daa0f21f","datavalue":{"value":"0734.68093","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q811138$A1A9C387-92EC-46B0-85E1-644A43BB84F1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c50d12121ada6ccea2599752cfbd0ed691119566","datavalue":{"value":{"entity-type":"item","numeric-id":811137,"id":"Q811137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q811138$596C050D-1DFA-4DC2-88FD-6B41C8773E59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7c1384f42ede1a938394d942ea31caae0e19e42e","datavalue":{"value":{"entity-type":"item","numeric-id":701798,"id":"Q701798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q811138$AF9E18C1-FA73-4B64-A807-76FDA50BFA20","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fcf622d4faaaf9eb501926768589cf6bc6e37689","datavalue":{"value":{"entity-type":"item","numeric-id":213743,"id":"Q213743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q811138$41831336-D76C-4768-823F-1C7535EE5B44","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q811138$C2450F65-9B7C-421D-B3A1-A2D0C338B624","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"23b5c52e7322c77f878550330668927977d27c15","datavalue":{"value":"https://eudml.org/doc/138419","type":"string"},"datatype":"url"},"type":"statement","id":"Q811138$864DCC40-7AE7-4F1D-AAD7-23C76985ADC7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f60faf780cf67247ae199739fdffa77ddd08900d","datavalue":{"value":"A simple polygon P is visible from a set \\(L\\subseteq P\\) if and only if for any point \\(y\\in P\\) there exists a point \\(x\\in L\\) such that xy\\(\\subseteq P\\). If P is visible from L, then L is called a cover of P. On the basis of classification of covers, problems of computing the number of components of minimal covers (covers of a certain type consisting of a minimal number of components) are characterized to be NP- hard.","type":"string"},"datatype":"string"},"type":"statement","id":"Q811138$FA5E4FB7-197B-43F9-B682-D3FE02FDC105","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q811138$4ADDAB22-14FE-42A2-A7C5-92BB2EB0E084","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q811138$1A47BAFE-E011-4F2E-A406-1AC648443B8D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"22042fbee6ab197e30122b3c9dc32d6476edccf4","datavalue":{"value":"4215404","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q811138$C74FF548-8FFB-4210-B7BD-B2E0287D3954","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ed28385b5c62eaaf3b0756eb74715fae1afa8293","datavalue":{"value":"simple polygon","type":"string"},"datatype":"string"},"type":"statement","id":"Q811138$12B70914-90FE-433D-8F14-96CD512C7000","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"20a763db13053be3a4822d197fe4416bdcf68133","datavalue":{"value":"classification of covers","type":"string"},"datatype":"string"},"type":"statement","id":"Q811138$F4905ED4-2488-434B-80DC-DB19B0D63CE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"be02a5081f405f5d39e1490d1c0b22301e0d854b","datavalue":{"value":"computing the number","type":"string"},"datatype":"string"},"type":"statement","id":"Q811138$5DDA532D-997F-4D53-B8A6-4D80AAF57C03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4320c5614e2dcd9f9634375e03f9e07019644c2c","datavalue":{"value":"components of minimal covers","type":"string"},"datatype":"string"},"type":"statement","id":"Q811138$3B6E9376-1362-4771-B555-EFBF1746AA82","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":"Q811138$90EE4973-FA34-4329-B946-8320AD5E5201","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cc37da0926f8ddae403bca88b8fea3917fba9790","datavalue":{"value":{"entity-type":"item","numeric-id":1200939,"id":"Q1200939"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c925e02b7732dd38a8c860837511a100da7602c2","datavalue":{"value":{"amount":"+0.8982729911804199","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":"Q811138$769F3807-3925-49E2-91D9-43B968BC3097","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3adb7ddacaaa1bddeb0f5783ad4bfb183177ec9f","datavalue":{"value":{"entity-type":"item","numeric-id":1825650,"id":"Q1825650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9552207b042963e664c9f8dab155c89758e88d42","datavalue":{"value":{"amount":"+0.8966981172561646","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":"Q811138$146AEB4E-CF4E-4BC2-A7A0-05E85B6DDBBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2768c681ffd3152165baa11d124fcea2d30369bd","datavalue":{"value":{"entity-type":"item","numeric-id":4304059,"id":"Q4304059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5f5e348fa8c972b5e97c57c34f265fe1d28fddef","datavalue":{"value":{"amount":"+0.8619380593299866","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":"Q811138$E712A7A9-15AE-41E0-84FD-9620C5363C5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9ca9ce296f3194c4934ba063a86b99de7089b4a1","datavalue":{"value":{"entity-type":"item","numeric-id":676264,"id":"Q676264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9571729cce2f42e13fe630548fe54d256401e74f","datavalue":{"value":{"amount":"+0.857990562915802","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":"Q811138$334A4515-AA47-4865-98C6-A8226A20BD10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a3e407c1b831ee2d57e6a8412ab8d0335e53ad4d","datavalue":{"value":{"entity-type":"item","numeric-id":4732109,"id":"Q4732109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3bab2350db621a3f6614b06ca274c52e0728a506","datavalue":{"value":{"amount":"+0.8505570292472839","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":"Q811138$914F4047-2CDE-45E2-9E29-9B85D486F164","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:811138","badges":[]}}}}}