{"entities":{"Q1699277":{"pageid":1710018,"ns":120,"title":"Item:Q1699277","lastrevid":72550428,"modified":"2026-04-14T05:39:46Z","type":"item","id":"Q1699277","labels":{"en":{"language":"en","value":"Routing in a polygonal terrain with the shortest beacon watchtower"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6840475"}},"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":"Q1699277$B7729AB3-DFDD-4D17-996B-CFC18872BA9A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b20e7328e057e23f5736c1b2bb5637617b1e5d5d","datavalue":{"value":{"text":"Routing in a polygonal terrain with the shortest beacon watchtower","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1699277$DF1C318E-DB00-4620-B2FF-8CC373E26B61","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"210a3f4de20a77150251514b1b0b7ad7378c436e","datavalue":{"value":"1396.65050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1699277$C6D492DB-D5E8-4C1F-AEE8-28110533AA73","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6f4fcc57d5cde98f774136dc1c3da0ce9868b8aa","datavalue":{"value":{"entity-type":"item","numeric-id":1699276,"id":"Q1699276"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1699277$B835C079-B49D-4AE8-8D79-7E54DA28D44A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"aaec84172c1017a432f6fd4d491b23a44a25ad07","datavalue":{"value":{"entity-type":"item","numeric-id":170487,"id":"Q170487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1699277$07640A5F-1447-44B2-A938-224A5DDB364C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8455035442168fbb99576351474dec2ff822256f","datavalue":{"value":{"entity-type":"item","numeric-id":247255,"id":"Q247255"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1699277$CEE85988-3795-4551-8C9C-C800797A5B14","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":"Q1699277$C5D0A661-738B-43E5-A7FA-3D9F701E2FCE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f287bdf783f35305500eed531b35fb7e704778e5","datavalue":{"value":{"time":"+2018-02-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1699277$E5DEBBA1-C723-4858-930D-FF2D43A17E64","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"267e0f6417f6a7f72b2a3eefd40ee8dfc3e5e67a","datavalue":{"value":"The problem of computing the shortest watchtower to guard a 2D terrain is approached in this paper, improving the existing techniques by using the properties of beacons. An \\(O(n \\log(n))\\) time algorithm that computes the shortest beacon watchtower is presented. The authors define the shortest beacon watchtower as a beacon on the upper endpoint of a vertical line segment erected on the terrain which can send and receive messages from any other point on the terrain. The authors start the construction of the new algorithm by elaborating algorithms to compute the beacon kernel and the inverse beacon kernel in a monotone polygon. The shortest beacon watchtower is computed by intersecting the kernel and inverse beacon kernel of the terrain polygon. The complexity of calculus of the new algorithm is discussed.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1699277$68E0548E-1FB7-4AD5-8ABE-F48284368E7A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d9a1bfcf9e07a8253dce89046bfb29494c13846d","datavalue":{"value":{"entity-type":"item","numeric-id":589467,"id":"Q589467"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1699277$4115590F-8005-4B8C-B813-A60C853E0AAD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2ce72165d993b0b8ed97728d731d2db2473b9554","datavalue":{"value":"65D18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1699277$4DDA9A50-9653-4CDC-B8E5-A2F71362FC4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1699277$DB54460A-E8E8-4BF0-841C-E83F7663D355","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ab9d815ee68abfead2d076269d6d191b00efe960","datavalue":{"value":"6840475","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1699277$976007E2-2C07-41C0-B302-033E05B5EB6F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"79c87ba26c35e85a7c05df027649b524c18782d7","datavalue":{"value":"beacon attraction","type":"string"},"datatype":"string"},"type":"statement","id":"Q1699277$76F5252A-088B-465D-BBA1-BBADFD4B6694","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4f4df519275bf0d81126b7c97bb9dbd3c783e763","datavalue":{"value":"greedy routing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1699277$A6C1236E-24ED-4F3C-B3BE-5764626610C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d7356341c6acaf5d84d7ab73495dfdc79996fb01","datavalue":{"value":"beacon kernel","type":"string"},"datatype":"string"},"type":"statement","id":"Q1699277$9DEF3CF0-669A-4110-A90B-A92F7C004838","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e9c4967c3057ecbb8cc3aaee747b0b8fc9b0785f","datavalue":{"value":"inverse beacon kernel","type":"string"},"datatype":"string"},"type":"statement","id":"Q1699277$B73AC2E7-AF1D-4086-B0F6-02EB7ACEA2B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3ddf50c7b8c2424c339cd29eb0a2af932c0c541a","datavalue":{"value":"beacon watchtower","type":"string"},"datatype":"string"},"type":"statement","id":"Q1699277$DEED3663-688A-4DDC-886C-83DCCE96A337","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":"Q1699277$3ED13D49-6F06-4089-AC70-F0A090DF5061","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"80e17ffcbea3602ec8fa1eb3d6c254b81ace324d","datavalue":{"value":"https://doi.org/10.1016/j.comgeo.2017.05.005","type":"string"},"datatype":"url"},"type":"statement","id":"Q1699277$4AB67A5E-8A90-42CD-9E98-B71D9C58989E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4304262fc10e97fd0b36016e6130e1f397e70d65","datavalue":{"value":"W2613478341","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1699277$6B760D6E-FC32-45FC-9D28-A62D5519CDDA","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4241f8308d167565bbead4d0eec3525ac106e02b","datavalue":{"value":{"entity-type":"item","numeric-id":5452284,"id":"Q5452284"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1699277$BCAEFB82-63F9-4BF8-BDE4-B6963606E2C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c97af6c36c1e0588e757d72bb5aa148f664f7d6","datavalue":{"value":{"entity-type":"item","numeric-id":2842154,"id":"Q2842154"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1699277$CEB6A72F-490F-48DC-873B-7A882E2093F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b275fe411bb7e44c71d4d673e35280be18b9bc5f","datavalue":{"value":{"entity-type":"item","numeric-id":1330785,"id":"Q1330785"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1699277$559B9223-7F41-4569-92B3-E4D56ECB1CF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8cb785b1fa00468f72c20fed51d4e390b8834f38","datavalue":{"value":{"entity-type":"item","numeric-id":582095,"id":"Q582095"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1699277$5E42126A-C954-4CBF-9C99-30AD42034AEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4eb8cc21703ca15dd783d9dceba1a9c26027bafe","datavalue":{"value":{"entity-type":"item","numeric-id":3922189,"id":"Q3922189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1699277$C8AA1E4B-B0C3-4A6C-9EBC-FA8E710094C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"132851b1e0bcf8d14d72162a7d91bcac0a3bd349","datavalue":{"value":{"entity-type":"item","numeric-id":2482906,"id":"Q2482906"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1699277$DA253576-4C47-4C0E-A1F0-7E3022385890","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3e181552ad0c28c9ecfff4f1863e5ea39b575420","datavalue":{"value":"10.1016/J.COMGEO.2017.05.005","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1699277$F164560E-B1B2-470D-B615-24E8BA0B7042","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"065ab503c0fac28dd78cf05603146a9d9b8bda5d","datavalue":{"value":{"entity-type":"item","numeric-id":1114400,"id":"Q1114400"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"54bda4f115605503f85d2e56afbd075917832c9a","datavalue":{"value":{"amount":"+0.7925437092781067","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":"Q1699277$BD5C0B61-2B09-4AEC-B52F-69DC67568C48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dd4877f1e6584d84c4e84d801b6ea23f3c5b7e2f","datavalue":{"value":{"entity-type":"item","numeric-id":2482906,"id":"Q2482906"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"71fba8a957dce44f165a079cdc19d77b68a873da","datavalue":{"value":{"amount":"+0.7882603406906128","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":"Q1699277$4F0D7BB1-2E58-4511-AE91-1DEF0EFC9ED4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"63dd12b6e896a8c54c28e50509d50f02d5a3ab6a","datavalue":{"value":{"entity-type":"item","numeric-id":4289632,"id":"Q4289632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"36624bd2285ba895624d64e0029bd6c8197cbd14","datavalue":{"value":{"amount":"+0.78272944688797","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":"Q1699277$B8A54E4D-841A-4925-AC48-4BA519FD6ECC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"289bd603a887acd2dae91d50822b03851ae326eb","datavalue":{"value":{"entity-type":"item","numeric-id":1807612,"id":"Q1807612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"828c1bec4506b0766a602282e7db38a1b6b6ebad","datavalue":{"value":{"amount":"+0.7755335569381714","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":"Q1699277$CEAEEE25-46B9-4ABB-BFC9-2A5F93DECD59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"56f11db6820773e1e31b281157eca831b0bb890d","datavalue":{"value":{"entity-type":"item","numeric-id":1607078,"id":"Q1607078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dcdd4fc109a89ceeee7b96a932ff1d499d09f8b8","datavalue":{"value":{"amount":"+0.7747529149055481","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":"Q1699277$0D4E76AB-0FE6-4EC2-B44F-A5267D0EEBF5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Routing in a polygonal terrain with the shortest beacon watchtower","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Routing_in_a_polygonal_terrain_with_the_shortest_beacon_watchtower"}}}}}