Костюк Ю. Л.

Графический поиск с использованием триангуляции и клеточного разбиения // Вестник Томского гос. ун-та, 2002, № 275, с. 147-152
http://www.inf.tsu.ru/library/Publications/2002/40.pdf
Электронная библиотека:




Рассматривается задача графического поиска на планарном подразбиении многоугольниками. Область поиска делится на квадратные клетки, а также триангулируется с учетом границ многоугольников. Вычисляется средняя длина поиска, оптимизируются параметры клеточного разбиения и триангуляции для равномерного и неравномерного распределения исходных точек. Предлагаются алгоритмы регионального поиска с линейной трудоемкостью.

Kostyuk Yu.L. Graphical Search Using Triangulation and Cellular Fragmentation. The task of graphical search on a planar subdivision by polygons is considered. The search region is divided into square cells and is triangulated subject to boundaries of polygons. The average search length is computed and parameters of cellular fragmentation and triangulation are optimized for uniform and non-uniform distribution of input points. The algorithms of regional search having linear time complexity are introduced.

Формат: PDF Размер: 392.7 Кбайт