{"entities":{"Q419369":{"pageid":421136,"ns":120,"title":"Item:Q419369","lastrevid":56892546,"modified":"2026-03-24T12:21:16Z","type":"item","id":"Q419369","labels":{"en":{"language":"en","value":"Memoryless routing in convex subdivisions: random walks are optimal"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6036378"}},"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":"Q419369$72170D6C-B783-4A77-BFAD-46AEF1FBF409","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"472ee015fd8b2d2bcd4d0eac16ec952546ead50e","datavalue":{"value":{"text":"Memoryless routing in convex subdivisions: random walks are optimal","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q419369$BFC2C73B-96F9-49ED-9663-83CD2442BA55","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"106565374db8dcb34866f02920c56f47e5c40e7b","datavalue":{"value":"1259.65038","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q419369$8A8DB4B6-D0AC-4D09-BCFD-D3D799482A8B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"34323737e65ec23e5b5f138b40eff9f6aeba6f57","datavalue":{"value":{"entity-type":"item","numeric-id":390138,"id":"Q390138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419369$AA101C3C-CA07-4E98-ABC4-CC77AA779740","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5ad270bb876f3a5e6f503d45a05fd7b45a710a3d","datavalue":{"value":{"entity-type":"item","numeric-id":223041,"id":"Q223041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419369$D09CAD2E-60ED-419D-A8A0-C8AF380B963C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"68ee3d60719c97b3f7244d7f2c477985e89e7464","datavalue":{"value":{"entity-type":"item","numeric-id":1242411,"id":"Q1242411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419369$60F4AA25-67D4-423E-A199-E9EAF836694F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"cd99316fa4f62a354c66fb1a826c5081505cdd08","datavalue":{"value":{"entity-type":"item","numeric-id":6770189,"id":"Q6770189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419369$C5D7EA1F-4630-4FAE-8131-97FD6CD3C23B","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":"Q419369$BB55F045-DE67-4143-9839-6AD9733514D3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"cce433cdcb3478d8106ca3fd120344ac0deb7f83","datavalue":{"value":{"time":"+2012-05-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q419369$F866E8EF-43A8-4A25-B207-2A3C23A2BB5F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6b67f40df97a23c6a6f29ac4c0668a2ab15e2c74","datavalue":{"value":"https://arxiv.org/abs/0911.2484","type":"string"},"datatype":"url"},"type":"statement","id":"Q419369$4D4FEE98-E614-4EED-A281-C17E6E8C69AD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e4c320760fc78a4a6b589ffd86a515c0d2696206","datavalue":{"value":"A memoryless routing algorithm is one in which the decision about the next edge on the route to a vertex \\(t\\) for a packet currently located at vertex \\(v\\) is made based only on the coordinates of \\(v, t\\), and the neighborhood \\(N(v)\\) of \\(v\\). In this paper, the authors study the limitations of such algorithms. In particular, it is shown that, for any (randomized) memoryless routing algorithm \\(\\mathcal A\\), there exists a convex subdivision on which \\(\\mathcal A\\) takes \\(\\Omega(n^2)\\) expected time to route a message between some pair of vertices. Since this lower bound is matched by a random walk, this result implies that the geometric information available in convex subdivisions is not helpful for this class of routing algorithms. The current paper also shows the existence of triangulations for which the Random-Compass algorithm proposed by \\textit{P. Bose} et al. in [Int. J. Comput. Geom. Appl. 12, No. 4, 283--295 (2002; Zbl 1152.68478)] and by \\textit{P. Bose} and \\textit{P. Morin} [SIAM J. Comput. 33, No. 4, 937--951 (2004; Zbl 1061.65014)] requires \\(2^{\\Omega(n)}\\) time to route between some pair of vertices.","type":"string"},"datatype":"string"},"type":"statement","id":"Q419369$D6762CA3-798E-452B-AB8F-AE5BFD4A3528","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2ce72165d993b0b8ed97728d731d2db2473b9554","datavalue":{"value":"65D18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q419369$0CD4597B-AC10-44C1-86CF-C4EE62088E3C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"78b9f795051415547e83673df941715560e601f2","datavalue":{"value":"6036378","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q419369$EF64B274-83E4-4B65-8685-7DDCE2229027","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"99613f4e815e51d9a5e5f985e9d0ddec0b39a3cf","datavalue":{"value":"geometric routing","type":"string"},"datatype":"string"},"type":"statement","id":"Q419369$5F9AA5A7-66E2-4C19-839C-E8B3DA71F650","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0192fb524376f45dfdd3eb1a809bf3cd5a9489","datavalue":{"value":"lower bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q419369$D9E2812B-ED41-4AA0-AA30-AB332C71C226","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4ee6cc203fe7fd9404e8829bd4b87b8061f49d9e","datavalue":{"value":"memoryless routing algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q419369$54F67B1D-A325-43AE-8599-E7BD3ACB2DF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"61d9fcb522122e79ba87536fad1b8187d3368d5d","datavalue":{"value":"convex subdivision scheme","type":"string"},"datatype":"string"},"type":"statement","id":"Q419369$9A0D8876-D390-4F37-8C7A-AA32E5521A01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"29f90cd83dad24fc82d0e60664cc695c283ac5bf","datavalue":{"value":"random walk","type":"string"},"datatype":"string"},"type":"statement","id":"Q419369$A0737336-B177-4DE2-AF06-A60AB6559817","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ed3c438d1bbf29e7f3ea72bbe28808806ee6da0f","datavalue":{"value":"random-compass algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q419369$9D12492C-EB68-48D3-915C-6FD866D8D0E4","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"eabcaa4115c7d203cf999b1d6476a35edc125dbe","datavalue":{"value":{"entity-type":"item","numeric-id":256764,"id":"Q256764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419369$DF618E2B-CE4D-49D3-B2A3-A16D53812D33","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":"Q419369$A78DF86B-8A8D-43AE-815C-84D1E059C30F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0393b2220e64b8eaa46ebdd5006dab37808a2a8f","datavalue":{"value":"W2122684646","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q419369$560EE671-B5D3-43E3-8978-0B3369DFD983","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"631b95c668b3fd1f675dae5b7bed596b40f7d251","datavalue":{"value":{"entity-type":"item","numeric-id":4818562,"id":"Q4818562"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419369$68F9591C-F687-45C7-BA22-DD72428CC318","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"841217de7d219db7feea3ce69ac810d5368b0893","datavalue":{"value":{"entity-type":"item","numeric-id":4651500,"id":"Q4651500"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419369$9228C1E0-B85B-458F-9815-B94460403053","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27ed627e4961fd9eb6057dc222b429acddae0055","datavalue":{"value":{"entity-type":"item","numeric-id":5681384,"id":"Q5681384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419369$EA527D92-28E7-4260-890E-12FCD3A277CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d05652188e444fc35e748b68b983451566933e27","datavalue":{"value":{"entity-type":"item","numeric-id":4856179,"id":"Q4856179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419369$238D4662-8F4D-4F17-B6FF-40CF9951316E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"28a12c8c66b8b878b84cdfdddb8ccd00e393dbf9","datavalue":{"value":{"entity-type":"item","numeric-id":4361347,"id":"Q4361347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419369$61D75867-3385-4B98-8A6A-553213D74169","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6cabcc6c33339345a4333f2979adeb19662b919a","datavalue":{"value":{"entity-type":"item","numeric-id":3581436,"id":"Q3581436"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419369$BABE2F34-2D1A-4053-B002-11EA91D34B9C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"321526a88c39f31b81c311d7854ecc29f9864397","datavalue":{"value":"10.1016/J.COMGEO.2011.12.005","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q419369$9081D96D-B3BC-444D-95DF-BDB370BD3276","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f94a39fbb0536b967875c823a73c8490bf9a2add","datavalue":{"value":{"entity-type":"item","numeric-id":4472479,"id":"Q4472479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0c47b07cc925abe06a46e4cdccd7c997f0235db3","datavalue":{"value":{"amount":"+0.8335068821907043","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":"Q419369$C9ED4DB9-A26B-48FA-94A1-71A6E5FBFEA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5abb486be9ea9bcba09873c671b40495253d7674","datavalue":{"value":{"entity-type":"item","numeric-id":4818562,"id":"Q4818562"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"33ab809a237e52afec8abd7e21da67d78fb8424e","datavalue":{"value":{"amount":"+0.8334498405456543","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":"Q419369$D1BEFB30-C703-445E-88B6-81D6E9C68E25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b61d34385e368cee7ffb319e9e866daf1f93aeb1","datavalue":{"value":{"entity-type":"item","numeric-id":4651500,"id":"Q4651500"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"738a979d1cc6c146e9f61bdcfc40f844d5b8aabe","datavalue":{"value":{"amount":"+0.8171620965003967","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":"Q419369$F275B6B6-6B45-486A-8EAB-77CA7EE4705B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"91390eba8d11f4cb64c5b206875934bec0f69b7e","datavalue":{"value":{"entity-type":"item","numeric-id":4511220,"id":"Q4511220"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"213590da29ea90b3ac5965e7bc01738ee339b25f","datavalue":{"value":{"amount":"+0.8039581775665283","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":"Q419369$A9373C52-15C8-490D-A03F-C9B7A121EBBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e477ad74efd335377af1628e951071fac340466e","datavalue":{"value":{"entity-type":"item","numeric-id":5175100,"id":"Q5175100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a29b6d231c9547dae20ed35b648eb4008533cef8","datavalue":{"value":{"amount":"+0.7999006509780884","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":"Q419369$70FFB858-C902-4D62-9B9C-4623EC22D966","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:419369","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:419369"}}}}}