Максимумы множества точек

Пять красных точек являются максимумами набора всех красных и желтых точек. Затененные области показывают точки, в которых доминирует по крайней мере один из пяти максимумов.

В вычислительной геометрии точка p в конечном множестве точек S называется максимальной или недоминируемой , если нет другой точки q в S , координаты которой все больше или равны соответствующим координатам p . Максимумы множества точек S — это все максимальные точки S. Задача нахождения всех максимальных точек, иногда называемая задачей максимумов или задачей множества максимумов , изучалась как вариант задач выпуклой оболочки и ортогональной выпуклой оболочки . Она эквивалентна нахождению границы Парето для набора точек и была названа Гербертом Фрименом задачей плавающей валюты на основе приложения, включающего сравнение относительного богатства людей с различными активами нескольких валют. ^[1]

Два измерения

Для точек в двух измерениях эта задача может быть решена за время O ( n log n ) с помощью алгоритма, который выполняет следующие шаги: ^{[1] [2]}

• Сортируем точки по одному из измерений координат ( например, по координате x )
• Для каждой точки, в порядке убывания по x -координате, проверьте, больше ли ее y -координата максимальной y -координаты любой ранее обработанной точки. (Для первой точки это бессмысленно ). Если это так, выведите точку как одну из максимальных точек и запомните ее y -координату как наибольшую из увиденных до сих пор.

Если координаты точек предполагаются целыми числами , то этот процесс можно ускорить с помощью алгоритмов сортировки целых чисел , чтобы получить то же асимптотическое время выполнения, что и алгоритмы сортировки. ^[3]

Три измерения

Для точек в трех измерениях снова можно найти максимальные точки за время O ( n log n ), используя алгоритм, аналогичный двумерному, который выполняет следующие шаги:

• Сортируем точки по одному из измерений координат ( например, по координате x )
• Для каждой точки, в порядке убывания по x -координате, проверить, является ли ее проекция на плоскость yz максимальной среди множества проекций множества точек, обработанных до сих пор. Если это так, вывести точку как одну из максимальных точек и запомнить ее y -координату как наибольшую из увиденных до сих пор.

Этот метод сводит задачу вычисления максимальных точек статического трехмерного набора точек к задаче поддержания максимальных точек динамического двумерного набора точек. Двумерная подзадача может быть эффективно решена с помощью сбалансированного бинарного дерева поиска для поддержания набора максимумов динамического набора точек. Используя эту структуру данных, можно проверить, доминируется ли новая точка существующими точками, найти и удалить ранее недоминируемые точки, которые доминируются новой точкой, и добавить новую точку к набору максимальных точек за логарифмическое время на точку. Количество операций дерева поиска линейно в ходе алгоритма, поэтому общее время составляет O ( n log n ) . ^{[1] [2]}

Для точек с целочисленными координатами первая часть алгоритма, сортировка точек, может быть снова ускорена целочисленной сортировкой. Если точки сортируются отдельно по всем трем их измерениям, диапазон значений их координат может быть уменьшен до диапазона от 1 до n без изменения относительного порядка любых двух координат и без изменения тождеств максимальных точек. После этого уменьшения координатного пространства проблема поддержания динамического двумерного набора максимальных точек может быть решена с использованием дерева Ван Эмде Боаса вместо сбалансированного бинарного дерева поиска. Эти изменения в алгоритме ускоряют его время работы до O ( n log log n ) . ^[3]

Более высокие измерения

В любой размерности d задача может быть решена за время O ( dn ² ) путем проверки всех пар точек на предмет доминирования одной из них над другой и вывода в качестве выходных данных точек, которые не доминируются. Однако, когда d является константой больше трех, это можно улучшить до O ( n (log  n ) ^{d  − 3}  log log n ) . ^[4] Для наборов точек, которые генерируются случайным образом, задачу можно решить за линейное время . ^{[5] [6]}

Ссылки

1. Preparata, Franco P. ; Shamos, Michael Ian (1985), «Раздел 4.1.3: Проблема максимумов множества точек», Computational Geometry: An Introduction, Texts and Monographs in Computer Science, Springer-Verlag, стр. 157–166, ISBN 0-387-96131-3.
2. Kung, HT ; Luccio, F.; Preparata, FP (1975), «О нахождении максимумов набора векторов» (PDF) , Journal of the ACM , 22 (4): 469–476, doi :10.1145/321906.321910, MR  0381379, S2CID  2698043.
3. Karlsson, Rolf G.; Overmars, Mark H. (1988), «Алгоритмы сканирующей строки на сетке», BIT Numerical Mathematics , 28 (2): 227–241, doi :10.1007/BF01934088, hdl : 1874/16270 , MR  0938390, S2CID  32964283.
4. Габов, Гарольд Н .; Бентли, Джон Луис ; Тарьян, Роберт Э. (1984), «Масштабирование и связанные с ним методы решения геометрических задач», Труды шестнадцатого ежегодного симпозиума ACM по теории вычислений (STOC '84) , Нью-Йорк, США: ACM, стр. 135–143, doi :10.1145/800057.808675, ISBN 0-89791-133-4, S2CID  17752833.
5. Бентли, Джон Л.; Кларксон , Кеннет Л.; Левин, Дэвид Б. (1993), «Быстрые линейные алгоритмы с ожидаемым временем для вычисления максимумов и выпуклых оболочек», Algorithmica , 9 (2): 168–183, doi :10.1007/BF01188711, MR  1202289, S2CID  1874434.
6. Дай, ХК; Чжан, СВ (2004), «Улучшенные линейные алгоритмы ожидаемого времени для вычисления максимумов», в Farach-Colton, Мартин (ред.), LATIN 2004: Теоретическая информатика, 6-й Латиноамериканский симпозиум, Буэнос-Айрес, Аргентина, 5-8 апреля 2004 г., Труды , Заметки лекций по информатике , т. 2976, Берлин: Springer-Verlag, стр. 181–192, doi :10.1007/978-3-540-24698-5_22, ISBN 978-3-540-21258-4, МР  2095193.