J

🥲 Problem

Imagine you want to buy a car. You go to different car dealers and check different cars. You decide to buy a car that is both fast and cheapest. How do you decide which car should you buy?

😋 Solution

The 2D Maxima Algorithm helps you to solve this problem. In this approach, you should take two values e.g. speed and price of the car. You will compare the speed and price of one car with other cars. Let's say x represents speed and y represents price. You need a car with the highest x value and lowest y value. In order to use the 2D Maxima Algorithm effectively you should do some math and put the value of y so that the higher the value of y the more cheap it should become. We can say the fast cheep car dominates the slow expensive car. We'll be listing all those cars that are not dominated by any other cars.

For example, you have the following values e.g. p1 = (2, 5), p2=(4,11), p3 = (4,4,), p4=(5,1), p5=(7,13), p6=(9,10), p7=(7,7), p8=(11,5), p9=(13,3), p10=(14,10), p11=(12,12), p12=(15,7) where p1,p2,p3,.....,pn are the name of the values which we say points.

Now let's formally describe this problem.

  • Let a point p in 2-dimensional space given by its integer coordinates, p=(p.x, p.y)

  • A point will be said to be dominated by any other point q if p.x<=q.x and p.y<=q.y

  • From the set of n points, P = {p1, p2, p3,...,pn} in 2-space, a point will be maximal if it is not dominated by any other point.

To solve the 2d-Maxima problem we can use 2 algorithms.

  1. Brute Force Algorithm
  2. Plane-sweep Algorithm

Let's first discuss brute force algorithm

1. Brute Force Algorithm For 2D Maxima

In this algorithm, we take a point and compare it with all other points to output the maximal points. This can output more than one maximal point. If we present the points on the graph it will show up something like below.

brute-force-2d-maxima

We'll get the maximam points i.e. (7,13), (12,12), (14, 10), (15, 7).

Brute Force 2D Maxima Psuodo Code

Copied!
MAXIMA(int n,Point P[1...n]) fori←1ton ntimes do maximal ← true for j ← 1 to n n times do if (i != j)&(P[i].x ≤ P[j].x)&(P[i].y ≤ P[j].y) then maximal ← false break if maximal then outputP[i].x,P[i].y

Brute Fore 2d Maxima in Javascript

Copied!
let points = [ [2, 5], [4, 11], [4, 4], [5, 1], [7, 13], [9, 10], [7, 7], [11, 5], [13, 3], [14, 10], [12, 12], [15, 7], ]; function maxima(n, p) { let maximalPoints = []; for (let i = 0; i < n; i++) { let maximal = true; for (let j = 0; j < n; j++) { if (i != j && p[i][0] <= p[j][0] && p[i][1] <= p[j][1]) { maximal = false; break; } } if (maximal == true) { maximalPoints.push(p[i]); } } return maximalPoints; } console.log(maximal(points.length, points));

2. Plane-sweep Algorithm For 2D Maxima

In-plane-sweep algorithm you have to sort the x-coordinate in ascending order. Then you'll use a stack data structure to find the maximal point. A stack is a data structure that is like putting the dishes onto one another. If you need to take a dish you'll need to remove all the dishes on top of it.

You'll then run a sweep line from left to right. Take one point and push it into the stack. Then go to the next point and if it is greater than the current element in the stack it will pop out the current element. And then push this new element into the stack. At the end, we'll have all the maximal points available in the stack.

This is how the execution of the algorithm will look like in real.

brute-force-2d-maxima
brute-force-2d-maxima
brute-force-2d-maxima
brute-force-2d-maxima
brute-force-2d-maxima
brute-force-2d-maxima
brute-force-2d-maxima
brute-force-2d-maxima
brute-force-2d-maxima

Plane Sweep 2D Maxima Psuodo Code

Copied!
PLANE-SWEEP-MAXIMA(n, P[1..n]) sort P in increasing order by x; stack s; fori←1ton do while (s.notEmpty() & s.top().y ≤ P[i].y) do s.pop(); s.push(P[i]); output the contents of stack s;

Plane Sweep 2d Maxima in Javascript

Copied!
// Stack class class Stack { // Array is used to implement stack constructor() { this.items = []; } // push function push(element) { // push element into the items this.items.push(element); } // pop function pop() { // return top most element in the stack // and removes it from the stack // Underflow if stack is empty if (this.items.length == 0) return "Underflow"; return this.items.pop(); } // peek function peek() { // return the top most element from the stack // but does'nt delete it. return this.items[this.items.length - 1]; } // isEmpty function isEmpty() { // return true if stack is empty return this.items.length == 0; } // printStack function printStack() { var str = ""; for (var i = 0; i < this.items.length; i++) str += `(${this.items[i]}), `; return str; } } function planeSweepMaxima(p) { let s = new Stack(); p.sort(function(a, b) { return a[0] - b[0]; }); for (let i = 0; i < p.length; i++) { while (s.isEmpty() == false && s.peek()[1] <= p[i][1]) { s.pop(); } s.push(p[i]) } console.log(s.printStack()); } let points = [ [2, 5], [4, 11], [4, 4], [5, 1], [7, 13], [9, 10], [7, 7], [11, 5], [13, 3], [14, 10], [12, 12], [15, 7], ]; planeSweepMaxima(points);

Applications of 2D Maxima

You can use 2D Maxima in different fields in real life. You can see some relevant fields below.

1. SkyLine Queries in database

In databases, we can use 2D maxima to retrieve skyline points from a database. For example, you are a real state agent. You want to find the best combination of price and square footage. You may want to use the following query to achieve this in the MySQL database.

Copied!
SELECT p1.x, p1.y FROM points p1 WHERE NOT EXISTS ( SELECT * FROM points p2 WHERE p2.x >= p1.x AND p2.y >= p1.y AND (p2.x > p1.x OR p2.y > p1.y) );

2. Resource Allocation in Cloud Computing

When you allocate resources in cloud computing environments. You might want to find the resources with low cost and higher performance. 2D Maxima could help you to achieve this.

3. Route Planning and Navigation

When you travel from one point to another in Geographical Information Systems. You may want to find the routes with the lowest cost and distance.

4. Investment Portfolio

You might think of investing in different companies. You may want to find the most suitable company which has higher pay rates and low risks.

5. E-Commerce Product Recommendation

In an e-commerce system, you may want to recommend products to users based on ratings, prices, and user preferences.

M. Mudassar
M. Mudassar
Sr. Software Engineer

As a software engineer, I take great pride in my ability to innovate and create efficient solutions. The satisfaction of seeing my code come to life and delivering products that exceed expectations is what drives me. I'm constantly learning and expanding my skill set to stay up-to-date with the latest trends and technologies. Collaboration is key in the software development process, and I thrive in diverse teams. Whether it's debugging existing code or developing new applications, I approach each project with enthusiasm and dedication, always striving to learn and improve.