Максимумы множества точек
В вычислительной геометрии точка 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 2 ) , проверяя все пары точек на предмет того, доминирует ли одна над другой, и сообщая в качестве выходных данных точки, над которыми не доминируют. Однако, когда d является константой больше трех, это можно улучшить до O ( n (log n ) д - 3 журнал журнал n ) . [4] Для наборов точек, генерируемых случайным образом, задачу можно решить за линейное время . [5] [6]
Ссылки
[ редактировать ]- ^ Jump up to: а б с Препарата, Франко П .; Шамос, Майкл Ян (1985), «Раздел 4.1.3: Проблема максимумов множества точек», Вычислительная геометрия: введение , Тексты и монографии по информатике, Springer-Verlag, стр. 157–166 , ISBN 0-387-96131-3 .
- ^ Jump up to: а б Кунг, HT ; Люччио, Ф.; Препарата, Ф.П. (1975), «О поиске максимумов набора векторов» (PDF) , Журнал ACM , 22 (4): 469–476, doi : 10.1145/321906.321910 , MR 0381379 , S2CID 2698043 .
- ^ Jump up to: а б Карлссон, Рольф Г.; Овермарс, Марк Х. (1988), «Алгоритмы развертки на сетке», BIT Numerical Mathematics , 28 (2): 227–241, doi : 10.1007/BF01934088 , hdl : 1874/16270 , MR 0938390 , S2CID 32964283 .
- ^ Габоу, Гарольд Н .; Бентли, Джон Луис ; Тарьян, Роберт Э. (1984), «Масштабирование и связанные с ним методы решения задач геометрии», Труды шестнадцатого ежегодного симпозиума ACM по теории вычислений (STOC '84) , Нью-Йорк, Нью-Йорк, США: ACM, стр. 135–143. , doi : 10.1145/800057.808675 , ISBN 0-89791-133-4 , S2CID 17752833 .
- ^ Бентли, Джон Л .; Кларксон, Кеннет Л .; Левин, Дэвид Б. (1993), «Быстрые линейные алгоритмы ожидаемого времени для вычисления максимумов и выпуклых оболочек», Algorithmica , 9 (2): 168–183, doi : 10.1007/BF01188711 , MR 1202289 , S2CID 1874434 .
- ^ Дай, Гонконг; Чжан, XW (2004), «Улучшенные линейные алгоритмы ожидаемого времени для вычисления максимумов», Фарах-Колтон, Мартин (редактор), 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 .