Algoritmo per il calcolo Punto Maximal in PointSet

Question

avevo questo come la domanda finale su un finale algoritmi (completato):

Dato un insieme di (x, y) punti P, lasciate M (P) l'insieme di maximal punti dato il seguente ordinamento parziale su P:

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

Così:

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

Fornire algoritmi che calcolano M (P) con complessità temporale O (nh), O (n log n) e O (n log h) (dove n = | P | e h = | M (P) |)

mio O (NH) algoritmo:

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 

mio O (n log n) algoritmo:

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 

Che cosa è un O (n log h) algoritmo?
La mia intuizione è che si tratta di una modifica del primo algoritmo, ma che utilizza una struttura dati intelligente (forse una modifica di un albero binario) che non ha bisogno di essere scansionata per ogni punto.

Esiste un tale algoritmo per un generale poset?
Questo avrebbe trovato le foglie di qualsiasi albero orientato dato un elenco di vertici e la ricerca costante di tempo se esiste un percorso diretto tra due vertici dati.

Answer 1

Questo è un davvero male domanda d'esame (a meno che il tuo istruttore ti ha parlato di uno dei O (log n h) algoritmi per convesso, nel qual caso è semplicemente male).

Il problema si chiama 2D MAXIMA ed è tipicamente il dominio dei geometri computazionali a causa della sua stretta relazione con gli scafi convessi di calcolo. Non riesco a trovare una buona descrizione di un algoritmo O (n log h) per il problema dei massimi, ma Timothy Chan's O(n log h) algorithm for 2D CONVEX HULL dovrebbe darti il ​​sapore.