The mapping of integer sets and Euclidean approximations

Authors

  • G.G. Ryabov
  • V.A. Serov

Keywords:

приближение к евклидовой метрике
простые ребра
метрическая окрестность
решеточный веер
веерная триангуляция
эквидистантный граф
топологический процессор

Abstract

The development of discrete models for representations of nonconvex parts of $R^3$ space and the solution of routing problems with a metric that approximates the Euclidean metric on these models continue to remain fundamental in the fields of robotics, geoinformatics, computer vision, and designing of VLSI. The paper deals with a lattice-cellular model. The main attention is paid to the mapping of the integer sets $Z^2$, $Z^3$, $Z^4$ onto itself, the construction of a lattice fan under a given accuracy of metric approximation, the decomposition of equidistant graphs, and the combined application of lattice and polyhedral models for a software system of metric-topological constructions.

New computational technologies

Downloads

Published

2007-01-09

Issue

Vol. 8 (2007): Issue 1.

Section

Section 1. Numerical methods and applications

Author Biographies

G.G. Ryabov

Lomonosov Moscow State University,
Research Computing Center

V.A. Serov

Lomonosov Moscow State University,
Research Computing Center

References

  1. Александров П.С. Комбинаторная топология. М.: Гостехиздат, 1947.
  2. Понтрягин Л.С. Основы комбинаторной топологии. М.: Наука, 1974.
  3. Касселс Дж. Введение в геометрию чисел. М.: Мир, 1965.
  4. Чандрасекхаран К. Введение в аналитическую теорию чисел. М.: Мир, 1974.
  5. Арнольд В.И., Гивенталь А.Б. Симплектическая геометрия. М.: ВИНИТИ, 2000.
  6. Рябов Г.Г. Дискретные конечные множества и их преобразования. М.: Изд-во ИТМ и ВТ, 1969.
  7. Kovalevsky V.A. Finite topology as applied to image analysis // Computer Vision, Graphics, and Image Processing. 1989. 46. 141-161.
  8. Рябов Г.Г. Модели коммутационных свойств конструкций ЭВМ. М.: Изд-во ИТМ и ВТ, 1989.
  9. Kovalevsky V.A. Finite topology and image analysis // Advances in Electronics and Electron Physics. 1992. 84. 197-259.
  10. Hamann B. A data reduction scheme for triangulated surfaces // Computer Aided Geometric Design. 1994. 11, N 2. 197-214.
  11. Couprie M., Bertrand G. Simplicity surfaces: a new definition of surfaces in Z3 // Proc. of SPIE (Vision Geometry VII). San Diego, 1998. 3454. 40-51.
  12. Kenmochi Y., Klette R. Surface area estimation for digitized regular solids // Proc. of SPIE (Vision Geometry IX). San Diego, 2000. 4117. 100-111.
  13. Vittone J., Chassery J. Recognition of digital naive planes and polyhedrization // Proc. of the 9th International Conference Discrete Geometry for Computer Imagery. Uppsala, 2000. 1953. 296-308.
  14. Kenmochi Y., Imiya A. Discrete polyhedrization of a lattice point set // Lecture Notes in Computer Science. Berlin-Heidelberg: Springer, 2001. 2243. 148-160.
  15. Strand R., Borgefors G. Weighted distance transforms for volume images digitized in elongated voxel grids // Pattern Recognition Letters. 2004. 25, N 5. 571-580.
  16. Klette R., Pan M. 3D topological thinning by identifying non-simple voxels // Lecture Notes in Computer Science. Berlin-Heidelberg: Springer, 2004. 3322. 164-175.
  17. Рябов Г.Г. Маршрутизация на решетчато-клеточных структурах // Вычислительные методы и программирование. 2004. 5, № 1. 107-117.
  18. Shuh E.Y., Wu Y.T. Three dimensional euclidean distance transformation and its application to shortest path planning // Pattern Recognition. 2004. 37, N 1. 79-92.
  19. Sitorn J.M., Borgefors G. Distance transforms for three-dimensional grids with non-cubic voxels // Computer Vision and Image Understanding. 2005. 100, N 3. 294-311.
  20. Рябов Г.Г. Метрические и топологические волны на решетках. М.: Изд-во Моск. ун-та, 2005.
  21. Рябов Г.Г Алгоритмические основы топологического процессора // Методы и средства обработки информации. Труды второй Всероссийской научной конференции. М.: Издательский отдел факультета вычислительной математики и кибернетики МГУ им. М.В. Ломоносова, 2005. 53-58.
  22. Desbrun M., Kanso E., Tong Y. Discrete differential forms for computational modeling // Proc. of ACM SIGGRAPH. Boston, 2006. 39-54.
  23. Alliez P., Cohen-Steiner D., Yvinec M., Desbrun M. Variational tetrahedral meshing // ACM Transactions on Graphics. 2005. 24, N 3. 617-625.
  24. Боровиков С.Н. Построение нерегулярных треугольных сеток на криволинейных гранях на основе триангуляции Делоне // Математическое моделирование. 2005. 17, № 8. 31-35.
  25. Четверушкин Б.Н., Гасилов В.А., Поляков С.В., Карташева Е.Л., Якобовский М.В. Пакет прикладных программ GIMM для решения задач гидродинамики на многопроцессорных вычислительных системах // Математическое моделирование. 2005. 17, № 6. 58-74.
  26. Klette R., Li F. Shortest paths in a cuboidal world // Lecture Notes in Computer Science. Berlin-Heidelberg: Springer, 2006. 4040. 415-429.
  27. Авраамова О.Д. Язык VRML. Практическое руководство. М.: ДИАЛОГ-МИФИ, 2002.
  28. Рябов Г.Г., Серов В.А. Среда для комплекса программ обработки воксельных структур // Информационные технологии. 2006. № 7. 22-26.
  29. Shouten T.E., Kuppens H.C., van den Broek E.L. Timed fast exact euclidean distance (tFEED) maps // Proc. of SPIE (Real-time imaging IX). San Jose, 2005. 5671. 52-63.