Introduction to 2-Dimension Maxima Problem

Suppose you want to buy a car. You want the pick the fastest car. But fast cars are expensive; you want the cheapest. You cannot decide which is more important: speed or price. Definitely do not want a car if there is another that is both faster and cheaper. We say that the fast, cheap car dominates the slow, expensive car relative to your selection criteria. So, given a collection of cars, we want to list those cars that are not dominated by any other.

Overview

  • Mathematical Defination

    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.

  • Solution

    Use of Brute-Force Algorithm for 2D Maxima Problem Let P = {p1, p2, . . . , pn } be the initial set of points. For each point pi, test it against all other points pj.

  • Analysis
I will get back to you ASAP.