Геом Поиск Локализация - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Геом Поиск Локализация. Доклад-сообщение содержит 18 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Вычислительная геометрия Лекция 6 Геометрический поиск Локализация точки Продолжение Метод трапеций (Зайделя) позже

Слайд 2

Описание слайда:

Геометрический поиск Планарные графы. Планарное прямолинейное подразбиение плоскости Представление ППЛГ. Реберный список с двойными связями Метод цепей (продолжение) Метод детализации триангуляции

Слайд 3

Описание слайда:

Геометрический поиск Планарные графы Планарное прямолинейное подразбиение плоскости Граф G = (V, E) называется планарным, если его можно уложить на плоскости без самопересечений. Планарное подразбиение или карта порождается прямолинейной укладкой ребер планарного графа на плоскости.

Слайд 4

Описание слайда:

Формула Эйлера: n + l = m + 2 G – связный плоский граф. T – его остовное дерево. В дереве m = n – 1, l = 1 и т. о. n + 1 = (n – 1) + 2. Не изменяя n, добавляем к остову ребро  образуется грань, т. е. m  m + 1, l  l + 1 и формула остается верной. Повторяем эту операцию. При этом формула Эйлера есть инвариант и останется верной после завершения таких шагов и получения графа G.  Стереографическая проекция

Слайд 5

Описание слайда:

Стереографическая проекция

Слайд 6

Описание слайда:

Следствие 1: Следствие 1: Во всяком выпуклом многограннике n + l = m + 2 Следствие 2а: Для связного планарного графа m  3n – 6 при n  3.

Слайд 7

Описание слайда:

Следствие 2б: Следствие 2б: Для связного планарного графа l  2n – 4 при n  3. Следствие 3: Графы K5 и K3,3 не планарны.

Слайд 8

Описание слайда:

Плоские триангуляции Триангуляция: все конечные грани – треугольники. Триангуляция множества точек – триангуляция выпуклой оболочки. Плоская триангуляция: связный плоский граф, каждая грань которого (в том числе и внешняя) – треугольник. В этом случае m = 3n – 6 и l = 2n – 4