{"entities":{"Q1947976":{"pageid":1958718,"ns":120,"title":"Item:Q1947976","lastrevid":43439416,"modified":"2025-07-25T20:51:36Z","type":"item","id":"Q1947976","labels":{"en":{"language":"en","value":"An optimal greedy routing algorithm for triangulated polygons"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6159334"}},"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":"Q1947976$EF79E2B9-B01A-4FF2-9738-3785F8A3B644","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"623a5dcfbeeb36daa9ef21a9d42f937c9f661445","datavalue":{"value":{"text":"An optimal greedy routing algorithm for triangulated polygons","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1947976$5101F45C-6382-44A4-8F70-45DCFB55090E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a563b68d186d7daf5c90f66f4b495e69ef3e8f11","datavalue":{"value":"1273.68281","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1947976$B3EAAD65-13FC-45F7-B206-8F0726E80742","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d986cff6622c35704cef135d24551ba22abe6059","datavalue":{"value":{"entity-type":"item","numeric-id":1947975,"id":"Q1947975"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1947976$CEF60DD6-7384-49CD-85EC-0C7B711B6F37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c8fed5f8514cff6c4b404f06640e44b22716b7ab","datavalue":{"value":{"entity-type":"item","numeric-id":283867,"id":"Q283867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1947976$C0F67C25-272C-47EF-899B-DA2DE31E026B","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":"Q1947976$4657346B-BF1B-4E81-9C41-770FA5CB6947","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ae17c4ecf184e2afd3c8b133626fdd9ae2ee388a","datavalue":{"value":{"time":"+2013-04-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":"Q1947976$DC13D489-33DB-45DD-B09A-4888D39D88C8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"65694f4fdd7cdeb35017e6d6fc7fe8df762dcace","datavalue":{"value":"In a greedy routing on a graph, each node forward messages to a neighbor that is closer to the destination. There are configurations of the graph where message delivery cannot always be guaranteed. A solution to this problems was to use a kind of virtual coordinates for the nodes instead of using real geometric coordinates. However, once the delivery guarantee problem was solved, another problem arose, that of achieving a simple representation of the virtual coordinates of each vertex.   In the recent paper [\\textit{H. Zhang} and \\textit{S. Govindaiah}, Lect. Notes Comput. Sci. 6681, 58--69 (2011; Zbl 1329.90155)] the authors observed that in order for greedy routing to work, there is no need to embed the graph in a metric space. Instead, they used greedy embedding of graphs into semi-metric spaces.  According with this approach, the main result in the paper under review is to show that any triangulated polygon with more than 3 vertices admits an optimal greedy routing algorithm, via a greedy embedding into an appropriate semi-metric space. The embedding is constructible in linear time and every node is representable in \\(O(\\text{deg}(\\nu)\\log(n))\\) bits, being \\(\\text{deg}(\\nu)\\) the degree of the node \\(\\nu\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1947976$640A615C-AC13-4864-B814-4659EA7B8237","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1947976$409B2C67-54D7-4DF0-85FA-237A8E29E8DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ca8c16691e9ec83d46a3995338b09d48ac9660ac","datavalue":{"value":"68M10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1947976$35F278F7-BACC-461B-921A-91ADBBB3FCE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f100e7e9b912dd320a0f918ece3ef4edbbe567fd","datavalue":{"value":"68M12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1947976$AAF225DA-2C19-4222-BD44-A106ED5DCB24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2ce72165d993b0b8ed97728d731d2db2473b9554","datavalue":{"value":"65D18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1947976$393B40DB-1DAB-4509-8885-DBD46873473F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"122520dbd595207e887fe2a2ae260d2bf7c3b84c","datavalue":{"value":"6159334","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1947976$89A9DBC7-3C5D-4B4D-84C2-252E61ABE53C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4f4df519275bf0d81126b7c97bb9dbd3c783e763","datavalue":{"value":"greedy routing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1947976$15003ABC-6AA7-491D-A13C-CC2CB7FCAE46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"34021ef787f4e28495d35f81de19ab2bcf2b70ec","datavalue":{"value":"stretch factor","type":"string"},"datatype":"string"},"type":"statement","id":"Q1947976$15CFE773-3323-4B9D-98E9-CF9EAA8E173F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"cddb9b56278140b4e4b3e2560891aea6b6cd8a4b","datavalue":{"value":{"entity-type":"item","numeric-id":478831,"id":"Q478831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1947976$A25C414F-D950-40AE-99FC-8BE8D1F73483","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":"Q1947976$95A9BB18-A8D8-4D41-B236-B613D1098C78","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7a53fa6022ba3c3c31a3942ef1c32d83e66c45a4","datavalue":{"value":"https://doi.org/10.1016/j.comgeo.2013.02.002","type":"string"},"datatype":"url"},"type":"statement","id":"Q1947976$41DCE526-5154-40A0-9897-1041C2BA9038","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e40b226a7068af8d524b9982b6d1defa97f60052","datavalue":{"value":"W1980738195","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1947976$47605B47-B004-45C0-A5E1-5CB5643DAEDA","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3383c7b957adf3abc8565433f9d9961b3977af1f","datavalue":{"value":{"entity-type":"item","numeric-id":5901462,"id":"Q5901462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1947976$8EC97F61-30AB-43B5-A15B-2CDF8A71E210","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a95d77faf3dc01380d132fe28f44ee14855cd5b9","datavalue":{"value":{"entity-type":"item","numeric-id":4281992,"id":"Q4281992"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1947976$2CAA1D74-A1CE-4E66-8935-664184FEEF4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe6001ea0d71940b476585cd1c664cfa541c0e27","datavalue":{"value":{"entity-type":"item","numeric-id":3602876,"id":"Q3602876"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1947976$84D4DBDC-2C4D-423A-B4FF-4B62230E6FDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"390b39ecdd0a6de344d479cdb5e38d36a7eaa6a7","datavalue":{"value":{"entity-type":"item","numeric-id":3579393,"id":"Q3579393"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1947976$66CFED90-A2C9-4A49-9ADE-C8F4038DA3A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"43b5a5e0f5f2b8dafa1aaa52f727207613f0c31d","datavalue":{"value":{"entity-type":"item","numeric-id":3611834,"id":"Q3611834"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1947976$BC283FCD-F8B0-4974-9C8E-C6C53A7906C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b91a4190faf3be2e2ea4b78c3ca57b950fc40573","datavalue":{"value":{"entity-type":"item","numeric-id":3652264,"id":"Q3652264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1947976$16B5AFA9-F9D2-4CC0-B2E4-DCE75AB88815","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fb560a4a92035e5a91d80bad95d6a85e688f6a8d","datavalue":{"value":{"entity-type":"item","numeric-id":603850,"id":"Q603850"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1947976$115A43BB-ADF6-4009-A327-1BF0087EFA2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed4543f77dd8afe15c4b2a6ea79b5e8240b8c9c8","datavalue":{"value":{"entity-type":"item","numeric-id":2575088,"id":"Q2575088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1947976$546935DD-997A-4F9F-AD17-223F1FC7AB9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b4d09c199d04ac01b7a6641fd89cf43278cebfba","datavalue":{"value":{"entity-type":"item","numeric-id":388089,"id":"Q388089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1947976$1A47C366-089D-4490-96FE-522072F9C9DE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"256e05a2c9825188d602d28abaef6b59ffb7920c","datavalue":{"value":"10.1016/J.COMGEO.2013.02.002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1947976$34D1B5D6-A23E-443A-A821-D11E0FEC3449","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"93b67209bec46a1d46c1ba00f9b0a6f0bb4e22a5","datavalue":{"value":{"entity-type":"item","numeric-id":388089,"id":"Q388089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e9a34d224f6cdcb9dc2857e3e3f914b789c64e2a","datavalue":{"value":{"amount":"+0.88793427","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1947976$9EF2E75E-7B08-4ABE-A13F-82224386E4FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5def910fff8654a121bcf0ece392b6931fb07735","datavalue":{"value":{"entity-type":"item","numeric-id":3004656,"id":"Q3004656"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"39b78d61f298393d8d221265f79753ecd32fcd95","datavalue":{"value":{"amount":"+0.88773304","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1947976$B5EE6A1E-D7BA-4546-862F-0E615998E511","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"411001c5d3a91b9a6dab244bd092a3f373998dfa","datavalue":{"value":{"entity-type":"item","numeric-id":3652264,"id":"Q3652264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"255b2b3ff187617d44e1d25a6d8841f04d6924d2","datavalue":{"value":{"amount":"+0.8436401","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1947976$91FC1F47-BA89-434E-AF35-0598F37E5583","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"76ce0da5085dbdd9bb15168bf0eda0b188baa8ba","datavalue":{"value":{"entity-type":"item","numeric-id":2913208,"id":"Q2913208"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4b5348503e8665265a259688209494180f766d46","datavalue":{"value":{"amount":"+0.8301196","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1947976$AA5F01E4-DDD1-4689-A8B8-4380DBF1F529","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"03eac51baf5ba0b2c1a416438154839de5039069","datavalue":{"value":{"entity-type":"item","numeric-id":3569082,"id":"Q3569082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dd2b7769ec7a790ea681ef31cbfac2a0ccbda493","datavalue":{"value":{"amount":"+0.8265956","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1947976$48241057-BCD0-4210-94D2-8F5FAB44F5F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8e10899947c3479996c9b43929459667a60d3b98","datavalue":{"value":{"entity-type":"item","numeric-id":603850,"id":"Q603850"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"125da941f5144eab5a781049be6ae946e178b2e2","datavalue":{"value":{"amount":"+0.82501984","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1947976$801DBDF2-12EE-4D48-8218-5A60605B68E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1c208dd9575fc58468b1e46b1200869bab5366fa","datavalue":{"value":{"entity-type":"item","numeric-id":896692,"id":"Q896692"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"42c389eaaea3d404223f34a86550602c08b66cc5","datavalue":{"value":{"amount":"+0.82462144","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1947976$E7235966-3C12-464C-A8C3-01725C0947EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9172683dcb3dc2bf1cbcb4d46b74ada5085c824b","datavalue":{"value":{"entity-type":"item","numeric-id":606989,"id":"Q606989"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a60d5631cb3ecd46b050ac4b9e31f1c0b18a2ea2","datavalue":{"value":{"amount":"+0.82323724","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1947976$E3E1CDC0-25C0-46FB-A07C-C897AB86A591","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"368a8a0b0c4138284d6b62f153b8f76f70200bdf","datavalue":{"value":{"entity-type":"item","numeric-id":2575088,"id":"Q2575088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"193ce23c206da3301d5da689d536fe3771d42770","datavalue":{"value":{"amount":"+0.815835","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1947976$5D0B6D4A-0422-4496-B409-39E909183170","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1947976","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1947976"}}}}}