{"entities":{"Q2419109":{"pageid":2429852,"ns":120,"title":"Item:Q2419109","lastrevid":53435858,"modified":"2026-01-24T23:11:37Z","type":"item","id":"Q2419109","labels":{"en":{"language":"en","value":"Connecting guards with minimum Steiner points inside simple polygons"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7060636"}},"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":"Q2419109$3D547AD9-411A-4884-8355-653BCB494B7E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"485c9dc66650d14740440e310dcdaa2c6c8bccd4","datavalue":{"value":{"text":"Connecting guards with minimum Steiner points inside simple polygons","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2419109$D7C47351-51C0-473B-8AE1-34D068899816","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"96f64ebd56e141454e73a746fee2bd8d1f8e6e67","datavalue":{"value":"1427.68325","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2419109$EEE82FCC-D717-405F-B436-2D08360F877C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e330a996c066e977d1217626b9d2eb9c57ced77e","datavalue":{"value":{"entity-type":"item","numeric-id":300223,"id":"Q300223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2419109$B8790FD6-5871-4959-8CF9-8F2CBE9C838B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d442703558e31374045d2950e9c97eee0cca98d5","datavalue":{"value":{"entity-type":"item","numeric-id":255266,"id":"Q255266"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2419109$36605F32-FB80-4C89-A056-63520E036E1C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2419109$606FE5CA-3D80-4B91-9FA3-8BBEA829C3A2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6120eae74d684c2ead20d43fdd3e39763954793c","datavalue":{"value":{"time":"+2019-05-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2419109$FEB769EB-90C0-4E28-89DE-CB268CDDD28D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6c8a326ef157463018beebee2af660edd80ce151","datavalue":{"value":"In the paper the authors study the problem of minimum connected Steiner guard set, which is a variant of the well-known art gallery problem. In this variant we have a simple polygon \\(P\\) and a finite set of points \\(Q\\) (the so-called terminal guards) inside \\(P\\). We are looking for a set \\(S\\) of minimum possible size such that the visibility graph of the points \\(Q \\cup S\\) with respect to \\(P\\) is a connected graph. The points from the set \\(S\\) are called the Steiner guards. Depending on the restrictions for the locations of the terminal or Steiner guards (i.e., the vertices of \\(P\\), the boundary of \\(P\\), any point inside \\(P\\)) the authors consider nine versions of the problem. In each case the authors show that the problem is NP-hard and present \\(O(1)\\) factor approximation algorithms for minimizing the number of Steiner guards. In the algorithms they build a graph over a finite set of points of \\(P\\) on which an instance of the Steiner Tree Problem is solved. The weights of vertices and edges in these graphs are equal. Thus, minimizing the number of vertices is equal to minimizing the number of edges. Using an \\(O(1)\\) approximation factor algorithms for the Steiner Tree Problem for such graphs the authors prove that the approximation factors of the proposed algorithms are \\(2.77\\) for the version restricted to the boundary of \\(P\\) and \\(1.39\\) for the version restricted to the set of vertices of \\(P\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2419109$8EDFFE4F-642C-4760-A6FC-FB78AA352574","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2419109$C160B6E1-4F8B-4D27-A801-B9CC98D282D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2419109$808BC5D0-5087-4AA5-A723-8F86E17AF9EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2419109$8430797A-A206-4573-AB21-076D3A243C1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2419109$E226F42E-7D53-45FF-B876-8893ADD8CA75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2419109$C3CADF39-3B61-45E0-B937-F7620E48931A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0183628d089e99a0ea4de84fcfc46e80f2314913","datavalue":{"value":"7060636","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2419109$732E03B3-1251-4D67-B688-316825400167","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7e0c8fe7f2179379b931f742f2b98a6f743f61c1","datavalue":{"value":"art gallery problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2419109$C10027F2-824B-444B-A598-8490881C1CFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"96164928d081ae9be3a4ee3ebadb261efb37632c","datavalue":{"value":"connected guard set","type":"string"},"datatype":"string"},"type":"statement","id":"Q2419109$392A9CD5-F84A-452B-A9A5-D00A475FA90B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7d5e4886aa4290eca104cd0d1da319d8b4d34c4","datavalue":{"value":"NP-hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q2419109$1D2F7908-C715-439B-B954-A5AE095305B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"da22488c2372d24f79c70ef7449d6664baa18130","datavalue":{"value":"Steiner guards","type":"string"},"datatype":"string"},"type":"statement","id":"Q2419109$ECE65BD5-B9BE-4800-8535-20D1576DBCCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b18d3948a42c7d1148336fe0006df600e3e0034b","datavalue":{"value":"Steiner tree problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2419109$6B60A7D7-016E-40DF-9F80-F879ACC980E1","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4e8aff2b8e51ed9533d593cc755cbfae6f7c82e5","datavalue":{"value":{"entity-type":"item","numeric-id":305012,"id":"Q305012"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2419109$CF414875-7BB1-482B-B495-98F2DBEB2215","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":"Q2419109$38EC93D8-2F60-440D-A0DA-AFE57F1EB452","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c92230f54c012afc8b225595d1574bc0b4943a62","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2018.12.008","type":"string"},"datatype":"url"},"type":"statement","id":"Q2419109$2AB9D67E-696B-47C9-A2E9-8A5675C715A5","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a44c3e1b3d8c5e2b459a0604a3076bb29ab5f56b","datavalue":{"value":"W2905030996","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2419109$061B4F04-1794-4E13-8B2B-61A1093387A1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"699e123b40e34ff16fa68ff29c5caeaeb10acb19","datavalue":{"value":{"entity-type":"item","numeric-id":4099997,"id":"Q4099997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2419109$EFD45AD6-5BB9-4B86-BFD3-7448E2823E3A","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":"Q2419109$C287216D-F4E2-4BD2-92FF-E1B9897ED531","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"69a1f5875b55db99ec84f2ef2c3c0cada8c8273f","datavalue":{"value":{"entity-type":"item","numeric-id":5444161,"id":"Q5444161"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2419109$8D7E00AE-017E-44FC-84CA-93D66189D692","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f575abb6ebc4078236ed705e236dd49f4a7554c7","datavalue":{"value":{"entity-type":"item","numeric-id":1122366,"id":"Q1122366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2419109$EDC81341-F72F-4B1A-B703-7E779D54AEBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"549e0aecc919c0e2cae322b388f586c1a547a289","datavalue":{"value":{"entity-type":"item","numeric-id":1854264,"id":"Q1854264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2419109$B799F9B3-0958-4737-A14E-942234F3D261","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"af810dbd31ec1bb889b5c4a65e1146d3c8189d58","datavalue":{"value":{"entity-type":"item","numeric-id":2875185,"id":"Q2875185"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2419109$139C52C3-47FC-426A-9DA8-7CAD4AC98913","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d8fc7cd3bf336112b9a4ea8ba4a049822456ac65","datavalue":{"value":{"entity-type":"item","numeric-id":5955147,"id":"Q5955147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2419109$915A3A15-132C-44D5-BBA7-43C825843921","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e0d45be44ebf51242cb045fd75fa6958e04798a9","datavalue":{"value":"10.1016/J.TCS.2018.12.008","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2419109$93EBC938-CC43-40F9-B826-FD415D0B6CD5","rank":"normal"}],"P1643":[{"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":"0f799617bf21007d732680b8322cdfe60de7dda8","datavalue":{"value":{"amount":"+0.8040767312049866","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":"Q2419109$B763AE5C-65E1-4283-82F3-D014FE702147","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8f019c22cc8a55158fa52fc8c4c10dda75db999e","datavalue":{"value":{"entity-type":"item","numeric-id":845875,"id":"Q845875"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"19be3fbd73a57d3f587d274d41bafff30c034c56","datavalue":{"value":{"amount":"+0.7917996048927307","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":"Q2419109$7F7ED251-D9E6-4B97-89F5-4D960E4CEA34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"75d74d46a74d524a83e407ff65e67f6e0129bbde","datavalue":{"value":{"entity-type":"item","numeric-id":5174948,"id":"Q5174948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"760cb611ac048bf6b908c0716eac38eb6a4ce58c","datavalue":{"value":{"amount":"+0.7901239395141602","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":"Q2419109$93140A83-FDAA-4471-9C67-1964F21F912B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0af65627e2dfb8e7f751dd15f9542f0d3f5af6da","datavalue":{"value":{"entity-type":"item","numeric-id":5411806,"id":"Q5411806"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b058fded6c847443b1dc04803ee9e8d5e9df296c","datavalue":{"value":{"amount":"+0.7883049249649048","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":"Q2419109$69474B40-11E1-4B7E-B395-11651DDC6903","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":"168b24ed6714f25217329f7f9024e09788c55e63","datavalue":{"value":{"amount":"+0.7850414514541626","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":"Q2419109$CFC44D4A-4EAE-4AC0-8F6B-9324E06253A7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2419109","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2419109"}}}}}