Максимумы набора точек - Maxima of a point set

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

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

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

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

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

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

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

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

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

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

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

Высшие измерения

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

Рекомендации

  1. ^ а б c Препарата, Франко П.; Шамос, Майкл Ян (1985), «Раздел 4.1.3: Проблема максимумов точечного множества», Вычислительная геометрия: введение, Тексты и монографии по информатике, Springer-Verlag, стр.157–166, ISBN  0-387-96131-3.
  2. ^ а б Кунг, Х. Т.; Luccio, F .; Препарата, Ф. (1975), «О нахождении максимумов набора векторов» (PDF), Журнал ACM, 22 (4): 469–476, Дои:10.1145/321906.321910, МИСТЕР  0381379, S2CID  2698043.
  3. ^ а б Karlsson, Rolf G .; Овермарс, Марк Х. (1988), "Сканирующие алгоритмы на сетке", BIT вычислительная математика, 28 (2): 227–241, Дои:10.1007 / BF01934088, HDL:1874/16270, МИСТЕР  0938390, S2CID  32964283.
  4. ^ Габоу, Гарольд Н .; Бентли, Джон Луи; Тарджан, Роберт Э. (1984), "Масштабирование и связанные с ним методы для геометрических задач", Материалы шестнадцатого ежегодного ACM Симпозиум по теории вычислений (STOC '84), Нью-Йорк, Нью-Йорк, США: ACM, стр. 135–143, Дои:10.1145/800057.808675, ISBN  0-89791-133-4, S2CID  17752833.
  5. ^ Бентли, Джон Л.; Кларксон, Кеннет Л.; Левин, Дэвид Б. (1993), "Быстрые линейные алгоритмы ожидаемого времени для вычисления максимумов и выпуклой оболочки", Алгоритмика, 9 (2): 168–183, Дои:10.1007 / BF01188711, МИСТЕР  1202289, S2CID  1874434.
  6. ^ Dai, H.K .; Чжан, X. W. (2004), "Улучшенные линейные алгоритмы ожидаемого времени для вычисления максимумов", в Фарах-Колтон, Мартин (ред.), ЛАТИН 2004: Теоретическая информатика, 6-й латиноамериканский симпозиум, Буэнос-Айрес, Аргентина, 5-8 апреля 2004 г., Труды, Конспект лекций по информатике, 2976, Берлин: Springer-Verlag, стр. 181–192, Дои:10.1007/978-3-540-24698-5_22, МИСТЕР  2095193.