{"entities":{"Q2477198":{"pageid":2487941,"ns":120,"title":"Item:Q2477198","lastrevid":73472187,"modified":"2026-04-14T16:07:30Z","type":"item","id":"Q2477198","labels":{"en":{"language":"en","value":"On guarding the vertices of rectilinear domains"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5249045"}},"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":"Q2477198$18CE4D39-4F45-4C6C-BE3A-A5F7D13CAAA6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a1e3663fbea8e486a663b9a2b4032d15bd1315f7","datavalue":{"value":{"text":"On guarding the vertices of rectilinear domains","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2477198$2B253482-9771-464D-A674-8D8663E1A60D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ec22db026b5cd1d37fdd5d79c2638fe1eb877e3d","datavalue":{"value":"1149.65015","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2477198$9785D460-06CA-4572-B826-A54A09CB7C4B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b5de52448e04f050e5b9f069b1a18cc236956934","datavalue":{"value":{"entity-type":"item","numeric-id":364842,"id":"Q364842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2477198$DCC9204C-156E-4B4E-B249-E95C20A2A565","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0b45180fb139b04a31d073cb42eb1738541bc681","datavalue":{"value":{"entity-type":"item","numeric-id":2477197,"id":"Q2477197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2477198$F1AA9889-72BA-4D5D-A506-29099BE3526E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"285beb29e5e30a7ba8792191178d7f52682884ef","datavalue":{"value":{"entity-type":"item","numeric-id":175378,"id":"Q175378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2477198$69ACF632-8B12-43B8-93F1-778273D9E4F0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"689f1c5bcb9279b19087f6d1d130b866f769f1ce","datavalue":{"value":{"time":"+2008-03-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2477198$BDBD1EDE-C91E-43A5-9D6E-87E84018F4B3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7790919a864451cacb4327f9df3f02835c16b37c","datavalue":{"value":"Two problems on visibility coverage are studied. One is the problem of guarding the vertices of a rectilinear polygon \\(P\\), which is considered in three different versions which are proved to be NP-hard. The three cases are the following: 1) guards may lie anywhere on the boundary of \\(P\\), 2) guards may lie only at vertices of \\(P\\), 3) guards may lie anywhere in \\(P\\).   A 1.5D rectilinear terrain, which is defined by an \\(x\\)-monotone chain \\(T\\) of horizontal and vertical line segments, is the region to be guarded in the second problem considered in the article. A connection is established between this problem and the problem of computing a minimum clique cover in chordal graphs. A \\(2\\)-approximation algorithm for the guarding problem is described.   Each part of the article is summarized in terms of a theorem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2477198$AACF1F9A-DCAD-48AC-83F6-9D0E691FD4FC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2ce72165d993b0b8ed97728d731d2db2473b9554","datavalue":{"value":"65D18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2477198$96A973AF-36FF-4859-B74F-CAA1E1DCE668","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"79b3bc872b6637176b35f9e46ac855febbf884f5","datavalue":{"value":"68W05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2477198$9D18451D-2927-44AD-947A-378AA3CF49EF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"503ffe1e3c33ce0a98a9e66f4db3838572671981","datavalue":{"value":"5249045","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2477198$2548C1A4-BB62-453B-B28D-6D69BB17B41C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0a2849fed3479edb812a736a871bd6b69ff9f050","datavalue":{"value":"geometric optimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q2477198$90431EE8-B00A-4246-AC9A-D68FA0123148","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"35d4289385a4d9b393bae1b3a5dddcae4512592c","datavalue":{"value":"guarding","type":"string"},"datatype":"string"},"type":"statement","id":"Q2477198$C865E7D8-C881-4AB0-8150-CB5E823DC984","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7d5e4886aa4290eca104cd0d1da319d8b4d34c4","datavalue":{"value":"NP-hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q2477198$AF18BA39-0186-4115-AD92-50C0FE0BB476","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc4837877785b4675d8ac1c6d4c911bcaf794e13","datavalue":{"value":"approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q2477198$E8F20C48-A815-4F52-A24C-D6CCADF5B01B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"633775a8c10b988ccc1084baa69ea145bbc617e6","datavalue":{"value":"visibility coverage","type":"string"},"datatype":"string"},"type":"statement","id":"Q2477198$F8FC81F1-28F2-483B-955D-21B894F55990","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a8bae6a282f7541d96b371eafdd2304c506d708b","datavalue":{"value":"piercing problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q2477198$7A3CD423-AE12-418C-82C2-0C7F265EEA5F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7ffa677918b324f746f69da6d13c929a6e1ecddd","datavalue":{"value":{"entity-type":"item","numeric-id":426996,"id":"Q426996"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2477198$1D707000-0C7C-4A58-AD48-F40458D53974","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":"Q2477198$55E59EE4-9121-4B81-A0E4-2785DB33110F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a117d608b617db68a0a8127b8c864f0ca55f9770","datavalue":{"value":"https://doi.org/10.1016/j.comgeo.2007.02.002","type":"string"},"datatype":"url"},"type":"statement","id":"Q2477198$127A2BF2-652B-4769-BD37-90B0572A4568","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b79f217fb304ce9c9a4a20850f3f21599683d1e0","datavalue":{"value":"W1970504456","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2477198$3815EF13-2246-4B80-9DEB-5DD01F94079A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"999de01410f6de5fa87c067d3ee44cac64a945e3","datavalue":{"value":{"entity-type":"item","numeric-id":2921708,"id":"Q2921708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2477198$E04C34E7-D866-4F73-848B-E648E81D5456","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5739b83f1fee4d9a80d23bc1ec7b1749f917eb16","datavalue":{"value":{"entity-type":"item","numeric-id":676572,"id":"Q676572"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2477198$E522DD6D-66BE-4684-A83E-F630ABBE4DA3","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":"Q2477198$E8502CF7-A0E3-4EEA-A256-6FEB6D4D0ECA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c06ee1013d42cb2a1b53edcb4d0b49da4de64ce9","datavalue":{"value":{"entity-type":"item","numeric-id":1394353,"id":"Q1394353"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2477198$635C7EB9-B76F-487C-9F5A-E5230B703AF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"caa4c43b4d2277a577c2f15eb05be56011995ffa","datavalue":{"value":{"entity-type":"item","numeric-id":5370605,"id":"Q5370605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2477198$8B469D51-82FE-4932-AC34-6BB0AB6C7A99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b43e3e48b388828a7b8aa17c3f81b7b754c93ecd","datavalue":{"value":{"entity-type":"item","numeric-id":773621,"id":"Q773621"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2477198$0FA87D19-ADFC-4733-B485-C272018EC935","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":"Q2477198$4DF74FD0-BE91-46E2-9B1F-0DB5D15639B5","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":"Q2477198$4B312527-EB0F-449E-81FF-792E691B38F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c33959e8c3fbe7080f98305389592daf8f06321e","datavalue":{"value":{"entity-type":"item","numeric-id":5634016,"id":"Q5634016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2477198$DECE341C-7F21-4D0B-80E6-FB6AF3950318","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"764f98ee422d323fb984284df27e0877c4f857ba","datavalue":{"value":{"entity-type":"item","numeric-id":5361582,"id":"Q5361582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2477198$340BB180-BBA3-4DED-8AC7-6DAD1A3BDEC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d243ba8d0bd5b390703e3b0396162a69459086ca","datavalue":{"value":{"entity-type":"item","numeric-id":1114399,"id":"Q1114399"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2477198$25923D13-2AE6-4E18-A8ED-543FF78F7B06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c059cbc74b5e58bb018d215ddf5cb31a40e35d5f","datavalue":{"value":{"entity-type":"item","numeric-id":4945512,"id":"Q4945512"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2477198$1240407A-5B24-4BA0-ABF7-B059CAA142F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c93b39121c297636317f3bb8fcc8fe805b9d00ea","datavalue":{"value":{"entity-type":"item","numeric-id":3525796,"id":"Q3525796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2477198$FDCFCB7A-C897-41FD-B5FD-10CB285E9227","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"35ec9c25c845666c672f8156370286dc32dbc225","datavalue":{"value":{"entity-type":"item","numeric-id":2754182,"id":"Q2754182"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2477198$B8A26E41-B242-4724-93F9-4D4CE599C441","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":"Q2477198$0F348CB1-8023-4DA2-86E3-76839196CEE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"26736971b71f38c87ce58e186943954df95eb066","datavalue":{"value":{"entity-type":"item","numeric-id":1837617,"id":"Q1837617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2477198$7A5EAB1A-B2EF-4149-A796-C533D3055EC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec5e921b4353c1a7c0359fb077421b5442f2ad52","datavalue":{"value":{"entity-type":"item","numeric-id":918225,"id":"Q918225"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2477198$E570184E-ED36-4FF3-B899-FAAE5BE62889","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"156fb61b7af9927e34b99cd368d5e07873490f4e","datavalue":{"value":{"entity-type":"item","numeric-id":5716760,"id":"Q5716760"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2477198$49E7C2FB-07F5-4160-8E3E-A1E00A43845A","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":"Q2477198$C7F34FC8-C1A6-4E86-B001-3CC0FF9DA792","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":"Q2477198$B0537BAA-D2C5-4EFD-999E-B31695531298","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e30b658d354ca025adfef84206ea6f6e8483233b","datavalue":{"value":{"entity-type":"item","numeric-id":4835529,"id":"Q4835529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2477198$CA6B5FF2-0EB1-46BB-B41A-316EA7C5477B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"914ac3f3e6da015fa5adc6009954b28551acde93","datavalue":{"value":{"entity-type":"item","numeric-id":4945523,"id":"Q4945523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2477198$2CA160A4-0B9E-45C6-8B91-4184B7EFB3AD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"018275558e00e05e541c3be046e7abe06a79be08","datavalue":{"value":"10.1016/J.COMGEO.2007.02.002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2477198$D4311CD9-8EE4-454C-B218-5903DF69D354","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c1969da7bb0fddc82f82d401e5ba6c891f215236","datavalue":{"value":{"entity-type":"item","numeric-id":5757890,"id":"Q5757890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e8cf73304ac12e141e9e3d14a9764c49f8fa9f51","datavalue":{"value":{"amount":"+0.993772566318512","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":"Q2477198$F048E20B-C4EE-4576-94A9-25156EB7A73B","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":"26f1c24acf8f04559b519714bbbd0ac00157c02d","datavalue":{"value":{"amount":"+0.8829705119132996","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":"Q2477198$7FCE0614-9FBA-48DB-8B17-D98BDB1A230F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5bc12ed83953d39a65a866a94845f5033543cb40","datavalue":{"value":{"entity-type":"item","numeric-id":3405972,"id":"Q3405972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"636828aab9568bf441b3585a735793bb5f3bfde3","datavalue":{"value":{"amount":"+0.8588694334030151","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":"Q2477198$A565C352-E786-4890-A779-08EAC39D0471","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"285b176d70f76ef650884ea698c53d53844fa98e","datavalue":{"value":{"entity-type":"item","numeric-id":3795225,"id":"Q3795225"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a0d6611c31339e74caaaedd5372aab85cdbcf118","datavalue":{"value":{"amount":"+0.8546157479286194","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":"Q2477198$A570EF17-915F-4686-AEFC-EC86FA5A763E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"548ac005f1ccb95a2f34f6da9d45e8f40c51acb3","datavalue":{"value":{"entity-type":"item","numeric-id":5946124,"id":"Q5946124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7557ee3403de24ac9af3e12340a46124304380d7","datavalue":{"value":{"amount":"+0.8427163362503052","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":"Q2477198$89FD5A35-51C6-4C8B-B0C0-8F74C29D0DA1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On guarding the vertices of rectilinear domains","badges":[]}}}}}