Задача

Формулировка задачи очень проста: для заданных n точек на плоскости найти пару точек, расположенных ближе друг к другу.

В начале 1970-х годов эту задачу рассматривали М. И. Шамос и Д. Хоуи в ходе проекта по поиску эффективных алгоритмов для базовых вычислительных примитивов для геометрических задач.

Эти алгоритмы заложили основу зарож- дающейся в то время области вычислительной геометрии и проникли в такие области, как компьютерная графика, обработка изображений, географические информационные системы и молекулярное моделирование. И хотя задача на- хождения ближайшей пары точек принадлежит к числу самых естественных алгоритмических задач в геометрии, найти для нее эффективный алгоритм оказы- вается на удивление сложно. Очевидно, существует решение O(n2) — вычислить расстояния между каждой парой точек и выбрать минимум; Шамос и Хоуи зада- лись вопросом, существует ли алгоритм, который был бы асимптотически более быстрым, чем квадратичный. Прошло довольно много времени, прежде чем был получен ответ на этот вопрос. Приведенный ниже алгоритм O(n log n) по сути не отличается от найденного ими. Более того, когда мы вернемся к этой задаче в главе 13, то увидим, что время выполнения можно дополнительно улучшить до O(n) за счет применения рандомизации.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Задача:

  1. ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
  2. 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
  3. Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
  4. ЗАДАЧА
  5. ЗАДАЧА: РЕШЕНИЕ
  6. Основные задачи.
  7. в) Задачи
  8. в) Задачи
  9. ПСИХОАНАЛИЗ: ЗАДАЧА
  10. ЗАДАЧА ДВИГАТЕЛЬНАЯ
  11. Основные задачи
  12. Правило решаемой психологической задачи.
  13. Задачи и упражнения