Routing on lattice-cellular structures

Authors

  • G.G. Ryabov

Keywords:

решетчатые графы
окрестности на решетке
целые точки
кратчайшие пути
метрика
волновой процесс

Abstract

An extension of the class of lattice graphs is considered. In order to become close to the Euclidean metric, inclusion of additional ribs with weights equal to the corresponding lengths of vectors in the Euclidean space is performed in a neighborhood on the lattice. A correspondence between the coordinates of nodes incident to the additional ribs and sequences of irreducible Farey-Cauchy fractions is established. An algorithm for constructing a set of the shortest paths on such a lattice is proposed. In essence, this algorithm models the «wave« process of constructing the field of all shortest paths from a set-source. Some estimates and examples are given to illustrate the computer realization of the algorithm proposed.

New computational technologies

Downloads

Published

2004-04-15

Issue

Vol. 5 (2004): Issue 1.

Section

Section 1. Numerical methods and applications

Author Biography

G.G. Ryabov

Lebedev Institute of Precise Mechanics and Computer Engineering (IPMCE RAS)

References

  1. Александров А.Д. Внутренняя геометрия выпуклых поверхностей. М.: Гостехиздат, 1948.
  2. Lee C.Y. Algorithm for path connections and its applications // IEEE Trans. 1961. T. EC-10.
  3. Зиман 3.Ю., Рябов Г.Г. Волновой алгоритм и электрические соединения. М.: Изд-во ИТМ и ВТ, 1965.
  4. Рябов Г.Г. Об одном алгоритме решения лабиринта на дискретном поле и его применении // ДАН. 1966. 166, № 5.
  5. Rosenfeld A., Pfaltz J. Distance functions on digital pictures // Pattern Recognition. 1968. N 1.
  6. Монтролл Э. Статистика решеток // Прикладная комбинаторная математика. М.: Мир, 1968.
  7. Рябов Г.Г. Связность и преобразования дискретных конечных множеств // Труды семинара струк. и лог. схем. 7 . М.: Изд-во ИТМ и ВТ, 1969.
  8. Gardner M. Mathematical games. New York: Scientific American, 1971.
  9. Чандрасекхаран Э. Введение в аналитическую теорию чисел. М.: Мир, 1974.
  10. Santalo L. Integral geometry and geometric probability. Boston: Addison Wesley, 1979.
  11. Wolfram S. Cellular automata as simple selforganizing systems. Shampain: Univ. Illinois Press, 1982.
  12. Рябов Г.Г. Научные основы создания комплексных САПР высокопроизводительных ЭВМ. Автореферат докт. дис. М.: ИТМ и ВТ, 1983.
  13. Wolfram S. Cellular automation supercomputing. Shampain: Univ. Illinois Press, 1982.
  14. Рябов Г.Г. Модели коммутационных свойств конструкций ЭВМ. М.: Изд-во ИТМ и ВТ, 1989.
  15. Das P. Lattice of octagonal distances in digital geometry // Pattern Recognition. 1990. N 11.
  16. Hadju A. and Hadju L. Velocity and distance of neighbourhood sequences // Acta Cybernetica. 2003. 16 .
  17. Y.Boykov Y. and Kolmogorov Y. Computing geodesics and minimal surfaces via graph cut // Trans. Inter. Conf. On Computer Vision. 2003.