algoritmo para calcular Puntos máxima en PointSet

Question

tuve esto como la última pregunta en una final de algoritmos (ahora completado):

Dado un conjunto de (x, y) señala P, dejar M (P) ser el conjunto de maximal puntos dada la siguiente ordenación parcial en P:

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

Así:

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

Proporcione algoritmos que calculen M (P) con complejidad de tiempo O (nh), O (n log n) y O (n log h) (donde n = | P | y h = | M (P) |)

Mi 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 

Mi 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 

¿Qué es un O (n log h) algoritmo?
Mi intuición es que es una modificación del primer algoritmo, pero utilizando una estructura de datos inteligente (tal vez una modificación de un árbol binario) que no necesita ser escaneada para cada punto.

¿Existe tal algoritmo para un general poset?
Esto encontraría en las hojas de cualquier árbol dirigido una lista de vértices y una búsqueda de tiempo constante de si hay una ruta dirigida entre dos vértices dados.

Answer 1

Esa es una muy, muy mal pregunta de examen (a menos que su instructor le ha hablado de uno de los O (n log h) algoritmos para el casco convexo, en cuyo caso es simplemente el mal ).

El problema se denomina 2D MAXIMA y es el dominio de los geometeoros computacionales debido a su estrecha relación con la computación de cascos convexos. No puedo encontrar una buena descripción de un algoritmo O (n log h) para el problema de los máximos, pero Timothy Chan's O(n log h) algorithm for 2D CONVEX HULL debería darle el sabor.