Formal Defination of 2-Dimension Maxima Problem

  • Let a point p in 2-dimensional space be given by its integer coordinates, p = (p.x, p.y).
  • A point p is said to be dominated by point q if p.x ≤ q.x and p.y ≤ q.y.
  • Given a set of n points, P = {p1, p2, . . . , pn} in 2-space a point is said to be maximal if it is not dominated by any other point in P.

The car selection problem can be modelled this way: For each car we associate (x, y) pair where x is the speed of the car and y is the negation of the price. High y value means a cheap car and low y means expensive car. Think of y as the money left in your pocket after you have paid for the car. Maximal points correspond to the fastest and cheapest cars.

The 2-dimensional Maxima is thus defined as

  • Given a set of points P = {p1 , p2, . . . , pn} in 2-space, output the set of maximal points of P, i.e., those points pi such that pi is not dominated by any other point of P.
Next