算法計算最大點在點集

我有這個作爲一個算法最終（現已完成）的最後一個問題：給定一組（X，Y）算法計算最大點在點集

點P，讓M（P）是集合給定上P上的以下部分排序maximal點：

(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)}

給出了計算具有時間複雜度O（nh），O（n log n）和O（n log h）（其中n = | P |和h = | M（P）|）

我的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

我爲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？
這將找到任何有向樹的樹葉給定一個頂點列表和恆定時間查找是否存在兩個給定頂點之間的有向路徑。

來源

2011-12-14 jacobhaven

你第一個算法不起作用 - 內循環從不執行，因爲M開始爲空 – 2011-12-14 07:34:45

這是一個真的很邪惡考試的問題（除非你的老師告訴你的O約一（N日誌1H）算法凸包，在這種情況下，它只是邪惡）。

這個問題被稱爲2D MAXIMA，因爲它與計算凸殼的密切關係，所以它通常是計算幾何的領域。我找不到一個關於最大值問題的O（n log h）算法的很好的描述，但Timothy Chan's O(n log h) algorithm for 2D CONVEX HULL應該給你一個風味。

來源

2011-12-14 15:56:31 Per

算法計算最大點在點集

回答

相關問題