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.


Published

2007-01-09

Issue

Section

Section 1. Numerical methods and applications

Author Biographies

G.G. Ryabov

V.A. Serov


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.