{"entities":{"Q635755":{"pageid":637603,"ns":120,"title":"Item:Q635755","lastrevid":63158169,"modified":"2026-04-11T10:59:47Z","type":"item","id":"Q635755","labels":{"en":{"language":"en","value":"Improved approximation for guarding simple galleries from the perimeter"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5941944"}},"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":"Q635755$AFD55C65-D05C-48E6-A349-5E8EBC86125B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e363dcd43b67ea5b4027b73be0639a4223175550","datavalue":{"value":{"text":"Improved approximation for guarding simple galleries from the perimeter","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q635755$7A2EE2F0-530F-4C18-8050-A128B8C200EB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e2b69ab76af4bdb0990ae0d7c38bba41a2133790","datavalue":{"value":"1226.68122","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q635755$454051AB-E894-4166-816E-0B47994C0817","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"03146bb8e17b3d6cc14817a371f8c48ba30cf452","datavalue":{"value":{"entity-type":"item","numeric-id":624377,"id":"Q624377"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q635755$156D9E21-9DD4-4C38-9033-FEF5C7CD1AA4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b6f367138a9ac2b85113cfed5a6fd5bedcc8944c","datavalue":{"value":{"entity-type":"item","numeric-id":178842,"id":"Q178842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q635755$D8835BD6-C60B-433B-8ECE-D71A1BC4C2CE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"364682ca68ff27747297558951f81941717a2938","datavalue":{"value":{"time":"+2011-08-23T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q635755$398874D0-E0C8-435F-A027-A84001BB02F6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"86b54b56850901e6e39de31e8eb2522ca5ddd9a7","datavalue":{"value":"In this paper, the authors present an \\(O(\\log \\log \\text{OPT})\\)-approximation algorithm for the problem of guarding a simple polygon with guards on the perimeter. The running time of this algorithm is polynomial in the number of vertices \\(n\\) of the polygon and the number of potential guard locations. If the set of potential guard locations is infinite, then the authors use the discretization technique of \\textit{A. Deshpande}, \\textit{T. Kim}, \\textit{E. D. Demaine} and \\textit{S. E. Sarma} [Lect. Notes Comput. Sci. 4619, 163--174 (2007; Zbl 1209.68582)]. Their algorithm is polynomial in \\(n\\) and \\(\\Delta\\), where \\(\\Delta\\) is the ratio between the longest and the shortest distances between vertices.","type":"string"},"datatype":"string"},"type":"statement","id":"Q635755$FF632474-4A5E-4996-AAFB-CCCCD82A2834","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"40dfd1103627e8665d2c838a53e6b6800d60f8f6","datavalue":{"value":{"entity-type":"item","numeric-id":264407,"id":"Q264407"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q635755$6907F205-45CB-4C51-8529-C918B29CA084","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q635755$40948423-333C-46AB-BEC7-72307EFC4591","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q635755$89135A4E-EF51-46F9-9ECF-1ED9C935C679","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f7ad69e69373c87ab7b0a38e100b80634c60d849","datavalue":{"value":"52A27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q635755$E42E6027-A934-477F-B83C-BB5A3CEEF07F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"374203e8674289349a2f5ca440ef9568344c23f8","datavalue":{"value":"5941944","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q635755$D974BA09-CA82-4596-BA1B-00DAFDFB40DB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7e0c8fe7f2179379b931f742f2b98a6f743f61c1","datavalue":{"value":"art gallery problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q635755$B56D407E-992A-4BD6-99EA-483E7C3A5261","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4ed2f31b6fe9f78e7a496dc9db47241acb5435f6","datavalue":{"value":"polygon guarding","type":"string"},"datatype":"string"},"type":"statement","id":"Q635755$2F254D90-8880-4B55-BAED-48DBA4417859","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0de600cf8191fa1f423fd01c9a02b172072a7391","datavalue":{"value":"approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q635755$6540B65D-7DFD-47B4-882C-0F4CCDCC56C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e181728ddf46ff122e8ac5f1321a3c7dc22d331e","datavalue":{"value":"epsilon-nets","type":"string"},"datatype":"string"},"type":"statement","id":"Q635755$2082489C-59AA-4789-AD80-F60BA5E1D132","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2b4231f99740052bb3d517d79722536fffca3a96","datavalue":{"value":"perimeter guards","type":"string"},"datatype":"string"},"type":"statement","id":"Q635755$25622713-8230-46E3-BB4D-6526D4B1A9F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0afa05215a9291040f9586af0465ac02251cdab4","datavalue":{"value":"vertex guards","type":"string"},"datatype":"string"},"type":"statement","id":"Q635755$CF27F1E3-5DA7-4B25-8AAA-6AC6E24FCA7B","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":"Q635755$3FBB218B-6E06-471D-A3EA-01C9B76C9B02","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b58f8ec970d2201483dcd01887dcfc5851c9c372","datavalue":{"value":"https://doi.org/10.1007/s00454-011-9352-x","type":"string"},"datatype":"url"},"type":"statement","id":"Q635755$4DAC5EA5-D87B-4743-9C74-94C63BF44F4F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8383fd4257d1ca4d50a3788373ca269fbe488606","datavalue":{"value":"W2139332235","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q635755$381BA263-69C3-47E5-92C9-42568C3355A9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"387553db542f2c25e00b5349259e5c106e8e8a22","datavalue":{"value":{"entity-type":"item","numeric-id":5390595,"id":"Q5390595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q635755$0D3648C7-09B0-4C20-AB84-1986305AF627","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5eceee8709c432551836aeb4f4aa8499755cd2c1","datavalue":{"value":{"entity-type":"item","numeric-id":3474905,"id":"Q3474905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q635755$57B1B970-82B6-4E7D-96DC-E96C8CA137E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ee14a9999276770a37970bc202ab687c7c6c0ec","datavalue":{"value":{"entity-type":"item","numeric-id":1862134,"id":"Q1862134"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q635755$60A0A486-9EC5-4451-BAAF-B9F6D927A0BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"83749458eedbcd9ca976877a83efacc450ae6cfd","datavalue":{"value":{"entity-type":"item","numeric-id":1906049,"id":"Q1906049"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q635755$2269506E-353B-4485-9BF5-F6311FCAB9B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a80eed9f379f185c9ca92aab1fa2ad3cc4463c9","datavalue":{"value":{"entity-type":"item","numeric-id":3887227,"id":"Q3887227"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q635755$2BEF1C5D-6663-406F-8EA8-1C9C0122B120","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"35f0c6c95f79c7cee88240ca4ec01c6c6d56139f","datavalue":{"value":{"entity-type":"item","numeric-id":3603524,"id":"Q3603524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q635755$90ACB651-7955-4583-AF27-46AB884B0C97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"96b76d38a8875306bb12d3e04c6724c3a79238fc","datavalue":{"value":{"entity-type":"item","numeric-id":845875,"id":"Q845875"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q635755$40280FBF-9D76-4C72-BE89-763C4ED6BCF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f2f36d050f58416eb06e3076c53ef57454a1609","datavalue":{"value":{"entity-type":"item","numeric-id":5946124,"id":"Q5946124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q635755$A166ED1A-5238-4C83-BCBE-06FD074EEFEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"783f5b77f65178466163307ca17329fb72140e4a","datavalue":{"value":{"entity-type":"item","numeric-id":3158517,"id":"Q3158517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q635755$4D688D70-77BB-4BB3-B481-4139B0649B00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q635755$690E83C4-B23B-4B52-AC17-3EE2CCD1E561","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c9f7431ddcd81252624824f67720f126de1e2170","datavalue":{"value":{"entity-type":"item","numeric-id":1380500,"id":"Q1380500"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q635755$B01D30B2-C8EE-4F2D-A7CF-DAE6A8DB5270","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"096ea5fec74316309bc41f9df83eee99d44a607a","datavalue":{"value":{"entity-type":"item","numeric-id":1184160,"id":"Q1184160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q635755$BC4BDBC8-AB5B-4B19-B530-7421E3AC8B4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da6a130fac4b3a2c7d09840d6dea725f6bcccd4e","datavalue":{"value":{"entity-type":"item","numeric-id":3723700,"id":"Q3723700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q635755$191F8EAD-89B6-4EEA-BFB8-41EE0DED9095","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a75892efb8c423df4e08c3a2522f9c8641bb850b","datavalue":{"value":{"entity-type":"item","numeric-id":3799261,"id":"Q3799261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q635755$A36334A7-278E-4C78-9E05-825651E78065","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"927dbf1a3adb1e111bc0c56e1db86cdcead56ead","datavalue":{"value":{"entity-type":"item","numeric-id":3967065,"id":"Q3967065"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q635755$74E3A73F-1B78-4EB6-B060-20AFF1F306C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18d5cfedfe66a3b5d774d6c8fbd31b828323bdab","datavalue":{"value":{"entity-type":"item","numeric-id":4527015,"id":"Q4527015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q635755$2948602F-B9DE-4374-A7A3-80FEB97569A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f98750da0d5c03342ed56a4aaf4fe51e130fed9","datavalue":{"value":{"entity-type":"item","numeric-id":1279960,"id":"Q1279960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q635755$8BDC9D37-6769-4A48-A617-CE7A4B0C67D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e55670eeffeb14e6ce51166fb8470acff9c12ef5","datavalue":{"value":{"entity-type":"item","numeric-id":5660314,"id":"Q5660314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q635755$EC754DA1-6A1D-4FD2-B9B0-773FB342212B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"181302890d76f99148f82e659810506732456f02","datavalue":{"value":"10.1007/S00454-011-9352-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q635755$26B13B36-40AD-443B-AE3D-4892E3F45D5C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e1f02f0fb313649ba9c2a41a7c7f69d85288ea85","datavalue":{"value":{"entity-type":"item","numeric-id":2340409,"id":"Q2340409"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7bf5b0e88aa7cde93154bd0375f8e89ae3589e1a","datavalue":{"value":{"amount":"+0.8731520175933838","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":"Q635755$6A9C39A4-F93A-4449-B056-A47DC6E3D03A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1801a30ed93aa14d161479ec67ccbbd9c76e12e9","datavalue":{"value":{"entity-type":"item","numeric-id":4580094,"id":"Q4580094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5def0d0dff79e517b72f1628577dedbae680625c","datavalue":{"value":{"amount":"+0.8458614349365234","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":"Q635755$2E2454AA-2438-4A97-B434-862226CDFA70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5b184fb355cbda5ef1c23234eb38205411149cf2","datavalue":{"value":{"entity-type":"item","numeric-id":968202,"id":"Q968202"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dabae9af0b51602affe535e99053d7eaa99fd1db","datavalue":{"value":{"amount":"+0.8451113700866699","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":"Q635755$E397990C-B4A5-4C8F-AAD6-844A20E2B07B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fba8ba518646e20b8a26a8d3007f455ef24e3c52","datavalue":{"value":{"entity-type":"item","numeric-id":2357167,"id":"Q2357167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6714670d786de6a04f170a3c7bce6b035154092f","datavalue":{"value":{"amount":"+0.8365460634231567","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":"Q635755$73691EB3-993F-4FED-9DB6-F7C32A01F84B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1a42e79bc54b13bd01ad3d8c51de58040919fef1","datavalue":{"value":{"entity-type":"item","numeric-id":2375947,"id":"Q2375947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2bac14adb233ba042f350420e9d74b21c105d8f2","datavalue":{"value":{"amount":"+0.8325963616371155","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":"Q635755$3BD19538-FF96-48A8-84D1-0A5BB1CA312F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Improved approximation for guarding simple galleries from the perimeter","badges":[]}}}}}