Алгоритм вычисления максимальных точек в Pointset - PullRequest
Новая
       15

Алгоритм вычисления максимальных точек в Pointset

5 голосов
/ 14 декабря 2011

У меня был последний вопрос об окончательном алгоритме (теперь завершенном):

Учитывая набор (x, y) точек P , пусть M (P) будет набором максимальным точками при следующем частичном упорядочении по P: 

(x,y) < (x',y') if and only if x < x' and y < y'.

Таким образом: 

M({(0,0),(1,1)})={(1,1)}
M({(0,0),(0,1),(1,0)})={(0,1),(1,0)}

Приведите алгоритмы, которые вычисляют M (P) с временной сложностью O (nh), O (n log n) и O (n log h) (где n = | P | и h = | M (P) |)

Алгоритм My O (nh): 

Declare M as a set of points
foreach p in P:
  addP = true
  foreach m in M:
    if(p < m):
      addP = false
      break
    if(m < p):
      M.remove(m)
  if(addP)
    M.add(p) //doesn't add if M contains p
return M

Алгоритм My O (n log n): 

Declare M as a set of points
Sort P in reverse lexicographic order
maxY := -inf
foreach p in P:
  if(p.y > maxY):
    M.add(p)
    maxY = p.y
return M

Что такое алгоритм O (n log h)?
Моя интуиция заключается в том, что это модификация первого алгоритма, но с использованием некоторой умной структуры данных (возможно, модификация двоичного дерева), которую не нужно сканировать для каждой точки.

Существует ли такой алгоритм для общего poset ?
Это позволило бы найти листья любого направленного дерева, учитывая список вершин и поиск по постоянному времени,направленный путь между двумя датьn вершин.

1 Ответ

6 голосов
/ 14 декабря 2011

Это действительно очень злой экзаменационный вопрос (если только ваш инструктор не рассказал вам об одном из O (n log h) алгоритмов для выпуклой оболочки, в этом случае это просто зло ) .

Проблема называется 2D MAXIMA и обычно является областью вычислительных геометров из-за ее тесной связи с вычислением выпуклых оболочек. Я не могу найти хорошее описание алгоритма O (n log h) для задачи о максимумах, но алгоритм O (n log h) Тимоти Чана для 2D CONVEX HULL должен дать вам представление.

...