О конструктивном вычислении сечений многомерного куба

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость новой

Детальная информация о работе

Выдержка из работы

О КОНСТРУКТИВНОМ ВЫЧИСЛЕНИИ СЕЧЕНИЙ МНОГОМЕРНОГО КУБА
Иван Гаврилович Казанцев
Институт вычислительной математики и математической геофизики Сибирского отделения РАН, 630 090, Новосибирск, проспект Академика Лаврентьева, 6, кандидат физикоматематических наук, доцент, старший научный сотрудник лаборатории обработки изображений Федерального государственного бюджетного учреждения науки Института вычислительной математики и математической геофизики Сибирского отделения РАН тел. +89 059 364 821, e-mail: kig@ooi. sscc. ru
В задачах визуализации многомерных массивов и изображений важным средством является визуализация сечений, вычисление которых требует рутинных комбинаторных вычислений. В работе предлагается быстрый аналитический метод вычисления центральных сечений. Работа частично поддержана грантом РФФИ 10−07−131.
Ключевые слова: гиперкуб, сечение, проекция.
ON A CONSTRUCTIVE COMPUTATION OF THE SECTION OF HYPERCUBE
Ivan G. Kazantsev
Institute of Computational Mathematics and Mathematical Geophysics SB RAS 6, prospect Akademika Lavrentjeva, Novosibirsk, 630 090, Russian Federation.
The problem of imaging of the multidimensional images and arrays includes an important part such as visualization of the sections which needs the routine combinatorial computations. In this work a fast analytical method of central projections calculations is proposed.
Key words: hypercube, section, projection.
В работе предлагается быстрый конструктивный некомбинаторный алгоритм вычисления фигуры пересечения Vкуба размерности N, или N-куба K = [-1,1]N 8 R и центральной плоскости / заданной двумя
ортонормированными векторами P, Q 0 I Основной идеей метода является сведение вычислений в пространстве R к операциям в двумерном пространстве плоскости / с использованием гномонической проекции. Фигура сечения V = K 1 / есть замкнутая выпуклая фигура, а именно центрально симметричный выпуклый многоугольник с максимально возможным числом 2N вершин и 2N сторон. Введем грани, или граничные (N-1)-кубы Fv, k=1,…, N, удовлетворяющие формуле: Fvk=((xi) xk = V1- -1 #x{ # 1, ink}. Объединение F = X Fvk является границей куба K [1]. Каждый граничный (N-1)-куб Fv имеет (2N-2) соседние грани и одну симметричную грань-антипод. Любые два соседних (^1)-куба из F имеют непустое пересечение в виде (^2)-кубов. Легко видеть, что каждое ребро многоугольника V принадлежит одной из граней или (N-lj-кубу Fv, а вершины V принадлежат одному из (N-2)-кубов.
Таким образом, вершины V являются точками пересечения плоскости / и некоторых (Ы-2)-кубов из границы F.
Задача вычисления сечения V для произвольной размерности N может классифицироваться как глобальный поиск точек пересечения плоскости / и (N-2)-кубов из границы F. Известно, что число L-кубов на границе N-куба есть 2n'-lN!/(L!(N-L)!). Поэтому в нашем случае традиционный подход потребует глобального перебора среди 2N (N-1) кандидатов на вершины многоугольника. Для больших размерностей этот метод становится затратным по времени.
Предлагаемый алгоритм вычисления V ассоциирует плоскость / с единичной окружностью C на этой плоскости и ортонормированными векторами P, Q ОС. Окружность C=C (P, Q) описывается параметром t 0[0, 2В) в форме
C (P, Q) = {S (t) = P cos t + Q sin t}.
Эти окружности лежат на единичной сфере S N1, которая находится во взаимно-однозначном соответствии с границей F Этот гомеоморфизм устанавливается с помощью гномонической проекции S N-1 на F:
Г: U = {щ} - U,
k umax
где U О S N-1, umax = max{ |u1|, …, |uN|}.
Приступим к описанию алгоритма. Пусть P = {pk} и Q = {qk}, k = 1 ,…, N. Построим 2N точек Tk = (pk, qk) и T-k = -(pk, qk) и их выпуклую оболочку
H = conv ({T±k}).
Мы можем доказать (доказательство за неимением места опускается), что число
M точек Hm, m =1, …, M, составляющих множество H, равно числу вершин V и эти вершины вычисляются в несколько некомбинаторных шагов. Сначала вычисляются точки Em такие, что OEm C HmHm+? (Hm упорядочены против часовой стрелки, с условием HM+1 = Н Д На следующем шаге вычисляются точки Dm = Pcos (3m) + Qsin (ym), где Sm являются угловыми координатами точек Em на плоской системе координат (p, q). Наконец, гномонические проекции
Vm = Г[ Am ]
точек Dm на границу FN-куба дают нам вершины Vm многоугольника V.
Для сравнения эффективности комбинаторного и конструктивного алгоритмов были проведены численные эксперименты. Использовался персональный компьютер с Pentium Dual Core CPU, 2.5 GHz под ОС Windows XP. Коды написаны в среде MATLAB.
Центральные плоскости / моделировались многократно (десять раз для каждой размерности N), используя генератор случайных ортонормированных N-векторов P и Q. Средние времена затрат переборного и нового алгоритмов для размерностей N=3,…, 100 для вычисления V фиксировались, используя функции МАТЛАБ tic и toc. Для вычисления выпуклой оболочки H
использовалась функция convhuHn. Сравнение показало что вычислительные временные затраты для нового алгоритма имеют очень медленный линейный рост для размерностей N & lt- 100 (Рис. 1 и Рис. 2), а средние времена вычислений V = [-1,1]^ 1 / для комбинаторного переборного алгоритма имеют порядок
О (^).
Рис. 1. Вычислительные затраты (в секундах) нового алгоритма и традиционного комбинаторного для N=3,.., 100 в сравнении с асимптотикой
ОN 5)
0. 01
0. 009
0. 008
«0. 007
§ 0. 006 Ф
w 0. 005 с
Ф 0. 004
Е
?- 0. 003 0. 002 0. 001
° 10 20 30 40 50 60 70 80 90 100
Dimension of N-Cube
Рис. 2. Временные затраты нового алгоритма при размерностях N=3,…, 100 (для
детальной визуализации рисунка!)
---New algorithm
! :.л i / •'- ^/-V * /* 1 t.
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. C. Zong. What is known about unit cubes // Bulletin of the American Mathematical Society. — 2005. — Vol. 42. — 181−211.
© И. Г. Казанцев, 2012

Показать Свернуть
Заполнить форму текущей работой