Скан Грэма

От / / Оставьте комментарий

Оглавление1 Сканирование Грэма1.1 Описание метода сканирования Грэма1.2 Алгоритм сканирования Грэма1.3 Временная сложность и псевдокод1.4 Модификации и численная надежность1.5 Полный текст […]

Convex hull algorithms, Алгоритмы выпуклой оболочки

Сканирование Грэма

  • Описание метода сканирования Грэма

    • Метод находит выпуклую оболочку множества точек на плоскости за время O(n log n) 
    • Назван в честь Рональда Грэхема, опубликован в 1972 году 
    • Алгоритм упорядочивает вершины выпуклой оболочки вдоль границы 

  • Алгоритм сканирования Грэма

    • Поиск точки с наименьшей координатой y, если есть несколько, выбирается точка с наименьшей координатой x 
    • Сортировка точек по углу, образованному с осью x, используя общий алгоритм сортировки, например, heapsort 
    • Определение “левого поворота” и “правого поворота” для точек, расположенных на одной прямой 
    • Определение выпуклости оболочки на основе перекрестного произведения векторов 

  • Временная сложность и псевдокод

    • Сортировка точек имеет сложность O(n log n), цикл с проверкой “правого поворота” имеет сложность O(n) 
    • Псевдокод использует функцию ccw для определения направления вращения точек 

  • Модификации и численная надежность

    • Модификация сканирования Грэма для сортировки по координате x 
    • Алгоритмы выпуклой оболочки хорошо продуманы и могут выдавать ответ с разумной погрешностью 
    • Graham-Fortune модификация решает проблемы конечной точности данных 

Полный текст статьи:

Скан Грэма — Википедия

Похожие статьи:

  1. Lucky Radix – Arc.Ask3.Ru Оглавление1 Сортировка по основанию1.1 История и применение1.2 Порядок цифр1.3 Сложность и производительность1.4 Специализированные варианты1.5 Применение к...
  2. Выпуклая функция – Arc.Ask3.Ru Оглавление1 Выпуклая функция1.1 Определение выпуклых функций1.2 Свойства выпуклых функций1.3 Неравенство Йенсена1.4 Определение выпуклости1.5 Альтернативные наименования1.6 Свойства...
  3. Выпуклая оболочка Оглавление1 Выпуклый корпус1.1 Определение выпуклой оболочки1.2 Визуализация и топологические свойства1.3 Экстремальные точки и компактные множества1.4 Оператор...
  4. Сортировка вставками Оглавление1 Сортировка вставок1.1 Основы сортировки вставками1.2 Наилучший, наихудший и средний случаи1.3 Связь с другими алгоритмами сортировки1.4...
  5. Y-быстрое трие Оглавление1 Y-быстрая пробка1.1 Структура y-fast trie1.2 Операции1.3 Поиск1.4 Преемник и предшественник1.5 Вставка1.6 Удаление1.7 Полный текст статьи:2...
  6. Алгоритмы выпуклой оболочки Оглавление1 Алгоритмы выпуклой оболочки1.1 Определение выпуклой оболочки1.2 История и сложность алгоритмов1.3 Известные алгоритмы выпуклой оболочки1.4 Оперативные...
  7. Сортировка слиянием Оглавление1 Сортировка слиянием1.1 Обзор сортировки слиянием1.2 Сложность сортировки слиянием1.3 Параллельная сортировка слиянием1.4 Многоходовая сортировка слиянием1.5 Многопоследовательный...
  8. Сортировка выбором Оглавление1 Сортировка по выбору1.1 Основы сортировки по выбору1.2 Структура и работа алгоритма1.3 Сравнение с другими алгоритмами1.4...
  9. Алгоритм сортировки Алгоритм сортировки Алгоритмы сортировки играют важную роль в обработке данных и используются для упорядочивания элементов.  Сортировка...
  10. Динамическая выпуклая оболочка Оглавление1 Динамический выпуклый корпус1.1 Динамическая задача о выпуклой оболочке1.2 Типы входных данных и модификации1.3 Методы и...
  11. Функция Invex Оглавление1 Вызывающая функция1.1 Определение выпуклой функции1.2 Свойства выпуклых функций1.3 Примеры выпуклых функций1.4 Инварианты выпуклых функций1.5 Инверсия...
  12. Разложение LU Оглавление1 Разложение LU1.1 Определение и свойства матрицы поворота1.2 Алгоритм частичного поворота1.3 Пример частичного поворота1.4 Общий алгоритм...
  13. Пузырьковая сортировка Оглавление1 Пузырьковая сортировка1.1 История и применение пузырьковой сортировки1.2 Эффективность и недостатки1.3 Вариации и параллельные версии1.4 Спор...
  14. Псевдокод Оглавление1 Псевдокод1.1 Определение и использование псевдокода1.2 Цели и применение псевдокода1.3 Стандарты и синтаксис псевдокода1.4 Сравнение с...
  15. Пирамидальная сортировка Оглавление1 Куча-мала1.1 Обзор алгоритма сортировки кучи1.2 Преимущества и недостатки1.3 Сравнение с другими алгоритмами1.4 Примеры и реализация1.5...
  16. Быстрая сортировка Быстрая сортировка Быстрая сортировка – популярный алгоритм сортировки, разработанный Кнутом в 1960 году.  Алгоритм использует разделение...
  17. Развернутое дерево Оглавление1 Раскидистое дерево1.1 Развернутое дерево1.2 Преимущества1.3 Недостатки1.4 Операции1.5 Реализация и варианты1.6 Анализ1.7 Обозначение big O1.8 Взвешенный...
  18. Квикхалл Оглавление1 Быстрый выпад1.1 Основы Quickhull1.2 История и разработка1.3 Двумерный алгоритм1.4 Расширение до трех измерений1.5 Псевдокод и...
  19. Топологическая сортировка Оглавление1 Топологическая сортировка1.1 Определение и применение топологической сортировки1.2 Алгоритм Кана1.3 Алгоритм Хопкрофта-Карпа1.4 Применение к задачам планирования1.5...
  20. Сортировка Оглавление1 Сопоставление1.1 Основы сортировки1.2 Алфавитный порядок1.3 Числовой порядок1.4 Другие типы сортировки1.5 Автоматизация сортировки1.6 Проблемы с числами...
  21. Слияние сортировки мэйнфреймов Оглавление1 Слияние сортировки мэйнфреймов1.1 Основные функции утилиты сортировки/объединения1.2 История и развитие1.3 Использование и дополнительные возможности1.4 Соревнование...
  22. Искусство компьютерного программирования Оглавление1 Искусство компьютерного программирования1.1 История создания1.2 Структура и содержание1.3 Особенности и инновации1.4 Признание и влияние1.5 Точность...

Оставьте комментарий