13
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Memoryless Routing in Convex Subdivisions: Random Walks are Optimal

      Preprint
      , , ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          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 neighbourhood, N(v), of v. The current paper explores the limitations of such algorithms by showing that, for any (randomized) memoryless routing algorithm A, there exists a convex subdivision on which 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 Bose etal (2002,2004) requires 2^{\Omega(n)} time to route between some pair of vertices.

          Related collections

          Author and article information

          Journal
          2009-11-12
          Article
          10.1016/j.comgeo.2011.12.005
          0911.2484
          1f72ef25-0302-4b1e-9b11-2a99e0122bc6

          http://arxiv.org/licenses/nonexclusive-distrib/1.0/

          History
          Custom metadata
          Computational Geometry: Theory and Applications, Volume 45, Issue 4, May 2012, Pages 178-185
          11 pages, 6 figures
          cs.CG

          Theoretical computer science
          Theoretical computer science

          Comments

          Comment on this article