Geek Answers Handbook

Algorithm for calculating maximum points in a set of points

I had this as the final question about the final algorithm (now completed):

Given the set of (x, y) points of P , let M (P) be the set of maximal points , given the following partial order on P: 

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

In this way:

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

Give algorithms that compute M (P) with time complexity O (nh), O (n log n) and O (n log h) (where n = | P | and h = | M (P) |)

My algorithm is 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 algorithm is 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

What is the O (n log h) algorithm?
My intuition is that it is a modification of the first algorithm, but uses some clever data structure (possibly a binary tree modification) that does not need to be checked for every point.

poset?
, , .

+5
1

( O (n log h) , > ).

2D MAXIMA - . O (n log h) , Timothy Chan O (n log h) 2D CONVEX HULL .

+6

More articles:


All Articles