{"entities":{"Q2391541":{"pageid":2402284,"ns":120,"title":"Item:Q2391541","lastrevid":51786599,"modified":"2026-01-20T01:01:15Z","type":"item","id":"Q2391541","labels":{"en":{"language":"en","value":"A tight bound for point guards in piecewise convex art galleries"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6193437"}},"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":"Q2391541$BC357C7E-BF9B-4CDE-81E3-EDAFB850F2A3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5b77fbeec82d2a6d4bc5f11a638a82a67c4c2957","datavalue":{"value":{"text":"A tight bound for point guards in piecewise convex art galleries","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2391541$C4D552A9-DA31-4380-A4AE-6792E9BF4758","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c863f06dd1fe7386f4bb7ad3bb546527e38592ba","datavalue":{"value":"1278.65017","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2391541$3703360C-F16C-4DA6-978E-7AE0DD1E8277","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0469e7e4cd464e7ba9d7db2ab07fc866a71d39bc","datavalue":{"value":{"entity-type":"item","numeric-id":322992,"id":"Q322992"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2391541$151C313F-BC27-4AFB-9789-CFA18E84445F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3a988ad1020b4a6ab1082581edf26c8f03761c8a","datavalue":{"value":{"entity-type":"item","numeric-id":344783,"id":"Q344783"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2391541$AACFC747-80E8-4E94-983C-91CFBEF6938B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c4c9be9ca23a2d959da50f0057a270a7fbc59409","datavalue":{"value":{"entity-type":"item","numeric-id":170450,"id":"Q170450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2391541$1AD4E1DC-33CD-4659-BB1F-275B1D949FA7","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":"Q2391541$E631C4E9-5F38-4193-B211-0164DD4E0270","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"683b08489c463bad988b3e086c3ff9e3b094bf28","datavalue":{"value":{"time":"+2013-07-31T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2391541$2BD788C9-9D8E-43F1-AF8F-23BF7000BBA6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3591ad6db1dce99e173190e6c2f1901158521cfa","datavalue":{"value":"http://www.sciencedirect.com/science/article/pii/S0925772113000370","type":"string"},"datatype":"url"},"type":"statement","id":"Q2391541$34D19A74-7C25-4696-85D4-BBB46534D4C5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a09c8b19ae99613d8cee58e65feb4429b6e39b25","datavalue":{"value":"The paper deals with a piecewise convex art gallery problem which is a generalization of the classical art gallery problem. In this type of art gallery problems, we have a set \\(A\\) of \\(n\\) vertices which is a simply connected region in the plane whose boundary consists of \\(n\\) convex arcs where \\(A\\) lies on the convex side of each arc. The problem is to find a minimum set \\(G \\subset A\\) of guards that jointly monitor \\(A\\).  The main result of the paper is a theorem which states that every piecewise convex art gallery problem with \\(n \\geq 1\\) vertices can be monitored by at most \\(\\lceil {n \\over 2} \\rceil\\) point guards (guards positioned anywhere in \\(A\\)). The proof of the theorem is based on a convex decomposition of the piecewise convex art gallery with \\(n\\) vertices into at most \\(n+1\\) convex cells. The set of convex cells is partitioned into at most \\(\\lceil {n \\over 2} \\rceil\\) subsets. Each of the subsets can be monitored by a single guard lying on a common boundary of the subsets.  Before the authors prove the theorem, they give some definitions and lemmas which are needed in the proof. They start with the definition of a convex decomposition of a curvilinear art gallery, a dual graph of a convex decomposition and give a construction of the so-called straightforward convex decomposition. Next, the authors give a definition of a nice decomposition and prove a lemma (Lemma 4) which is used in the proof of the main theorem and which states that every piecewise convex gallery with \\(n \\geq 2\\) vertices has a nice decomposition. The proof of the lemma gives a construction of the nice decomposition. The authors also study the dual graph of the nice decomposition. Then, they prove a lemma (Lemma 11) which states that a curvilinear art gallery with \\(n \\geq 2\\) vertices and a nice decomposition can be monitored by \\(\\lceil {n \\over 2} \\rceil\\) point guards. The proof of the lemma is a constructive one, it gives a method of finding the point guards. Using Lemmas 4 and 11, the authors give a short proof of the main theorem. Finally, they present a simpler proof of a theorem given by \\textit{M. I. Karavelas, C. D. T\u00f3th} and \\textit{E. P. Tsigaridas} [Comput. Geom. 42, No. 6--7, 522--535 (2009; Zbl 1169.65019)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q2391541$5123DF10-4E7E-4D08-8B29-1EA30F0C8971","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2ce72165d993b0b8ed97728d731d2db2473b9554","datavalue":{"value":"65D18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2391541$FFC14525-6F25-4FF0-81D8-F190A43C4C3C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3ce55d495003bddf1c7193af0f2b0b6896eb8ee5","datavalue":{"value":"6193437","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2391541$56E16B9A-2087-4A18-B5FF-CE562E327CAB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c1a842b4f4882bc8cbc9e7e5ded22ca87149cc32","datavalue":{"value":"art gallery","type":"string"},"datatype":"string"},"type":"statement","id":"Q2391541$5E8FEFEF-7B77-443A-95D0-9A4E6DB54F32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7bfd605e8d1eec2e403cfe1b9f8fb6385b43b4a0","datavalue":{"value":"visibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q2391541$E2D1135F-8F2E-4B1D-BD76-D90D0E59A4AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"77f6b6104c5bc6728bdf2fdebffaf8a308e1cbc0","datavalue":{"value":"convex decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q2391541$55D738E6-C0FD-4360-86A9-D8D07C14067D","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":"Q2391541$28EEDC2D-A410-49CD-A7B2-DBFEB6377D1A","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":"Q2391541$2F905F02-C146-4B03-BB58-DE8FE1883D02","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"78e7aa8ce154d809f5c93c1117d18f6fbd2bcf09","datavalue":{"value":"W2096467882","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2391541$C393E68B-756C-4C8B-8D8C-DDFF9171C106","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"215962f50cb9eca58cceb09ffd3675aec9943ad3","datavalue":{"value":{"entity-type":"item","numeric-id":652620,"id":"Q652620"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2391541$E85F7699-0910-47F9-BE95-D015F5C3F370","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a4a1ba71c5df8e0b9dbceffc2f6752b09ef1a85","datavalue":{"value":{"entity-type":"item","numeric-id":3964035,"id":"Q3964035"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2391541$83442BC3-F5F2-498C-80CB-281E5B237F24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a14bb5de49d1025f33147045f216b73559caa6b2","datavalue":{"value":{"entity-type":"item","numeric-id":3721846,"id":"Q3721846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2391541$8C655811-25C6-49AF-BC8E-F0C8D381D035","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":"Q2391541$BD00184E-B413-4F9D-BCFF-61AB2B318EF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9adfe3a61d3a52386945e30186e12f90be5931bf","datavalue":{"value":{"entity-type":"item","numeric-id":911324,"id":"Q911324"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2391541$C60EE6BD-80D9-482C-9FDB-9D4529F0A181","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f3fdde788538675a5d7d8479040594354c62d281","datavalue":{"value":{"entity-type":"item","numeric-id":1105375,"id":"Q1105375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2391541$E0D024EF-52BA-4ABD-92AD-E54504C6C23E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1f127a9f827f6bea6ecce5e152f921a2b67013d","datavalue":{"value":{"entity-type":"item","numeric-id":1823611,"id":"Q1823611"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2391541$959EAEF7-0862-4F2D-B67C-AEECA212A99D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b62d421a9b6e8ef636869b625aeb657b4f6b2d98","datavalue":{"value":{"entity-type":"item","numeric-id":3602853,"id":"Q3602853"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2391541$FD02D8A9-2B92-48CB-9C0F-7821A0DD9C20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b046a819e8eb07d9f15687ae4a1bed411a7a949b","datavalue":{"value":{"entity-type":"item","numeric-id":709066,"id":"Q709066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2391541$EAC260F6-0B5A-41AA-8FC2-04FF41278E17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9465667aeaa4796a9a1e69622676cb6898b6ea1","datavalue":{"value":{"entity-type":"item","numeric-id":924067,"id":"Q924067"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2391541$AF616190-5F4F-44EF-8B9B-8AC40095BDF6","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":"Q2391541$C7DA3732-50DE-43C6-8B68-31D4F6765ACE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aad572227c4e9f5a3e496e88ca93baec545aae19","datavalue":{"value":{"entity-type":"item","numeric-id":4016400,"id":"Q4016400"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2391541$B8628A2D-F672-4EBB-B52F-C919C117E7D9","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":"Q2391541$A27A4B6E-D6E9-448F-9383-C5BFB7FCD7EB","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":"Q2391541$A434094D-066D-4BA7-84A1-7A24F3D66404","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"44d26966280431dc173c707e44320adba6007328","datavalue":{"value":"10.1016/J.COMGEO.2013.04.004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2391541$1D937C54-B961-4746-93D3-4D3C8A6C7CC0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"968e6c9d02d5d997f80b53d3605b191914b3579c","datavalue":{"value":{"entity-type":"item","numeric-id":924067,"id":"Q924067"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c5c45dcc46c2ed9b4543ae9b32341cc4d2e1256f","datavalue":{"value":{"amount":"+0.9249044060707092","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":"Q2391541$40A36021-ACEC-469D-A6F1-777D0FB036CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ae59b7b24a9bda20673c94fa1f19283ce12db660","datavalue":{"value":{"entity-type":"item","numeric-id":4038729,"id":"Q4038729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eae7b7da4540fbbad9f157515bf85492da8ac6ca","datavalue":{"value":{"amount":"+0.8324726819992065","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":"Q2391541$114AF4B9-947E-4368-8E58-92507CDB06C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"91b9ee8dd07ef73ee06458eedb446b3a4a881eaa","datavalue":{"value":{"entity-type":"item","numeric-id":2490667,"id":"Q2490667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eae7b7da4540fbbad9f157515bf85492da8ac6ca","datavalue":{"value":{"amount":"+0.8324726819992065","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":"Q2391541$D30F93BA-55C1-4BD2-8B49-A361B503B430","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d98ce9f881285f89dc82a7b70756b751b357c57c","datavalue":{"value":{"entity-type":"item","numeric-id":709066,"id":"Q709066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"154e5780494db879487ef22f86a3d2f7ed51dabe","datavalue":{"value":{"amount":"+0.8242936730384827","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":"Q2391541$60B12A83-8B11-4E0D-9951-3977A347919D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"520d2e8a07912dd89417546ca95db24eb87d477a","datavalue":{"value":{"entity-type":"item","numeric-id":1410595,"id":"Q1410595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"48b06910f0ce88c5371598e1389a20b6784ad107","datavalue":{"value":{"amount":"+0.8168781399726868","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":"Q2391541$D4E0BA05-CAF9-46AB-A3F1-C2C86A3A3905","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2391541","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2391541"}}}}}