Алгоритм Бентли Оттмана

Интернет магазин китайских планшетных компьютеров

Компьютеры - Алгоритм Бентли Оттмана - Анализ

23 января 2011

Оглавление:
1. Алгоритм Бентли Оттмана
2. Обработка вертикальных отрезков
3. Алгоритм
4. Анализ

Пусть n — число отрезков, $m \left$ — число отрезков, пересекающих точку q. Тогда время на инициализацию Q равно $O \left$ , на инициализацию T — $O \left$ . На поиск всех отрезков, проходящих через точку q и обновление Q, требуется $O \left \log n \right)$ времени. На обновление T также $O \left \log n \right)$ времени. Суммарно: $O \left \log n \right) = O \left \right) = O \left \log n \right)$ , где k — число точек пересечения $\left = O \left \right)$ . $k = O \left$ .

Память $O \left$ , благодаря тому, что удаляются точки пересечения отрезков, которые перестали быть соседними, иначе было бы $O \left$ , где $k = O \left$ .

<<< Алгоритм DDA-линии

Алгоритм Брезенхэма >>>

Компьютерное аппаратное обеспечение
Вычислительные комплексы
Компьютерные данные
Компьютерные журналы
Классы компьютеров
Компьютеры

Программное обеспечение
Производители компьютеров
Профессии в ИТ
Системное администрирование
Компьютерный сленг
Списки компьютерных терминов

Человеко-компьютерное взаимодействие