Декомпозиция на значительно удаленные пары: различия между версиями

Понятие декомпозиции на значительно удаленные пары, предложенное Кэллаханом и Косарайю [3], нашло широкое применение при решении задач о близости точек на евклидовой плоскости. Пара множеств точек (A, B) является ''значительно удаленной с коэффициентом c'', если расстояние между A и B не менее чем в c раз превышает диаметры A и B. Декомпозиция на значительно удаленные пары для множества точек состоит из множества значительно удаленных пар, «покрывающих» все пары различных точек; иначе говоря, любые две различные точки принадлежат к разным множествам некоторой пары. Кэллахан и Косарайю [3] показали, что для любого множества точек на евклидовой плоскости и любой константы c <math>\ge 1 \;</math> всегда существует декомпозиция на значительно удаленные пары с коэффициентом c (c-WSPD) с линейным числом пар. Этот факт оказался исключительно полезным для разработки алгоритмов с близким к линейному временем выполнения для решения самых разных задач – таких как вычисление k-ближайших соседей, потенциальных полей для системы из N тел, геометрических остовов, приближенных минимальных остовных деревьев и многих других. Декомпозиция на значительно удаленные пары также широко использовалась для разработки эффективных динамических и параллельных алгоритмов, а также алгоритмов на базе внешней памяти.