Граница Парето в 3D за O(NlogN) время

Продолжая тему поста «Граница Парето в 2D за O(NlogN) или O(N) время«, я решил реализовать и опубликовать аналог в трёхмерном пространстве (обобщение на три показателя качества). Соответствующий алгоритм также описан в книге Препараты и Шеймоса «Вычислительная геометрия: Введение» вслед за двумерным алгоритмом. Алгоритм основан на принципе заметания объёма плоскостью.

  1. Отсортировать точки по координате z.
  2. Проходя точки в порядке сортировки от максимального значения координаты z до минимального, добавлять их в статус заметающей плоскости.

Статус плоскости хранит упорядочение (например, по координате x) подмножества доминирующих точек и представляет собой сечение плоскостью z = const области пространства, доминируемой перебранными на данный момент точками («лесенку», см. рисунок ниже). При добавлении новой точки P в статус:

  1. Ищем в статусе точку R, ближайшую справа к P.
    • Если она лежит выше P, то отбрасываем P и выходим.
    • Если её нет, либо она лежит ниже P, то вставляем P в статус и переходим к п.2.
  2. Ищем в статусе точку L, ближайшую слева к P и находящуюся выше P.
  3. Удаляем из статуса все точки в интервале (L, P). Если L не найдена, то удаляются все точки слева от P.
  4. Сообщаем P как недоминируемый элемент.

граница Парето 3D статус

Статус может быть реализован в виде сбалансированного двоичного дерева (желательно, прошитого, возможно, уложенного в массив), тогда, как нетрудно видеть, алгоритм найдёт все недоминируемые точки за O(NlogN) время. Была написана реализация на C++, позволяющая реализовать статус в виде политики, передаваемой параметром шаблона, либо воспользоваться std::set или любым совместимым аналогом.

Реклама

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s

%d такие блоггеры, как: