Table of contents
🥲 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.
- Brute Force Algorithm
- 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.
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.
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.
