Thuật toán để tính điểm tối đa trong Pointset

Question

Tôi có điều này là câu hỏi cuối cùng về một trận chung kết giải thuật (nay là hoàn thành):

Cho một tập của (x, y) chỉ P, chúng ta hãy M (P) là bộ maximal điểm cho thứ tự từng phần sau trên P:

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

Như vậy:

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

Đưa ra các thuật toán tính toán M (P) với độ phức tạp thời gian O (nh), O (n log n) và O (n log h) (trong đó n = | P | và h = | M (P) |)

My O (nh) thuật toán:

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) thuật toá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 

một O là gì (n log h) thuật toán?
Trực giác của tôi là nó là một sửa đổi của thuật toán đầu tiên, nhưng sử dụng một số cấu trúc dữ liệu thông minh (có lẽ là một sửa đổi của một cây nhị phân) mà không cần phải được quét qua cho mỗi điểm.

Có một thuật toán cho tổng quát poset không?
Điều này sẽ tìm thấy các lá của bất kỳ cây được chỉ định nào đưa ra danh sách các đỉnh và tìm kiếm thời gian liên tục cho dù có một đường dẫn trực tiếp giữa hai đỉnh đã cho hay không.

Answer 1

Đó là một thực sự thực sự ác thi câu hỏi (trừ khi giảng viên của bạn nói với bạn về một trong những O (n log h) thuật toán cho thân lồi, trong trường hợp này đó là chỉ đơn thuần ác).

Vấn đề được gọi là 2D MAXIMA và thường là miền của geometers tính toán vì mối quan hệ chặt chẽ của nó với vỏ máy tính lồi. Tôi không thể tìm thấy một mô tả tốt về một thuật toán O (n log h) cho vấn đề maxima, nhưng Timothy Chan's O(n log h) algorithm for 2D CONVEX HULL sẽ cung cấp cho bạn hương vị.