Skyline Algorithm Algorithm
The Skyline Algorithm is an innovative multi-criteria decision-making method designed to identify the best or most optimal solutions from a set of alternatives based on multiple, often conflicting, criteria. Introduced by Boris Babenko, it has gained significant popularity in various fields such as database management, decision support systems, and recommendation systems, among others. The algorithm works by finding a set of dominating points (the skyline) in a multi-dimensional dataset, which represent the best trade-off solutions among the considered criteria. These dominating points are the ones that are not dominated by any other point in terms of all the considered criteria.
The algorithm operates by iteratively comparing data points in the dataset based on the given criteria and retaining only those that dominate over the others. A point is said to dominate another point if it is better or equal in all criteria and strictly better in at least one criterion. The Skyline Algorithm efficiently narrows down the dataset to a smaller set of superior points (the skyline) by eliminating non-dominating points. This smaller subset of points can then be used for further analysis or decision-making. The Skyline Algorithm is particularly useful in situations where there is no single optimal solution due to the conflicting nature of the criteria or where decision-makers need to evaluate trade-offs among different alternatives.
package divideconquer;
import java.util.ArrayList;
import java.util.Comparator;
/**
* @author dimgrichr
* <p>
* Space complexity: O(n)
* Time complexity: O(nlogn), because it is a divide and conquer algorithm
*/
public class SkylineAlgorithm {
private ArrayList<Point> points;
/**
* Main constructor of the application.
* ArrayList points gets created, which represents the sum of all edges.
*/
public SkylineAlgorithm() {
points = new ArrayList<>();
}
/**
* @return points, the ArrayList that includes all points.
*/
public ArrayList<Point> getPoints() {
return points;
}
/**
* The main divide and conquer, and also recursive algorithm.
* It gets an ArrayList full of points as an argument.
* If the size of that ArrayList is 1 or 2,
* the ArrayList is returned as it is, or with one less point
* (if the initial size is 2 and one of it's points, is dominated by the other one).
* On the other hand, if the ArrayList's size is bigger than 2,
* the function is called again, twice,
* with arguments the corresponding half of the initial ArrayList each time.
* Once the flashback has ended, the function produceFinalSkyLine gets called,
* in order to produce the final skyline, and return it.
*
* @param list, the initial list of points
* @return leftSkyLine, the combination of first half's and second half's skyline
* @see Point
*/
public ArrayList<Point> produceSubSkyLines(ArrayList<Point> list) {
// part where function exits flashback
int size = list.size();
if (size == 1) {
return list;
} else if (size == 2) {
if (list.get(0).dominates(list.get(1))) {
list.remove(1);
} else {
if (list.get(1).dominates(list.get(0))) {
list.remove(0);
}
}
return list;
}
// recursive part of the function
ArrayList<Point> leftHalf = new ArrayList<>();
ArrayList<Point> rightHalf = new ArrayList<>();
for (int i = 0; i < list.size(); i++) {
if (i < list.size() / 2) {
leftHalf.add(list.get(i));
} else {
rightHalf.add(list.get(i));
}
}
ArrayList<Point> leftSubSkyLine = produceSubSkyLines(leftHalf);
ArrayList<Point> rightSubSkyLine = produceSubSkyLines(rightHalf);
// skyline is produced
return produceFinalSkyLine(leftSubSkyLine, rightSubSkyLine);
}
/**
* The first half's skyline gets cleared
* from some points that are not part of the final skyline
* (Points with same x-value and different y=values. The point with the smallest y-value is kept).
* Then, the minimum y-value of the points of first half's skyline is found.
* That helps us to clear the second half's skyline, because, the points
* of second half's skyline that have greater y-value of the minimum y-value that we found before,
* are dominated, so they are not part of the final skyline.
* Finally, the "cleaned" first half's and second half's skylines, are combined,
* producing the final skyline, which is returned.
*
* @param left the skyline of the left part of points
* @param right the skyline of the right part of points
* @return left the final skyline
*/
public ArrayList<Point> produceFinalSkyLine(ArrayList<Point> left, ArrayList<Point> right) {
// dominated points of ArrayList left are removed
for (int i = 0; i < left.size() - 1; i++) {
if (left.get(i).x == left.get(i + 1).x && left.get(i).y > left.get(i + 1).y) {
left.remove(i);
i--;
}
}
// minimum y-value is found
int min = left.get(0).y;
for (int i = 1; i < left.size(); i++) {
if (min > left.get(i).y) {
min = left.get(i).y;
if (min == 1) {
i = left.size();
}
}
}
// dominated points of ArrayList right are removed
for (int i = 0; i < right.size(); i++) {
if (right.get(i).y >= min) {
right.remove(i);
i--;
}
}
// final skyline found and returned
left.addAll(right);
return left;
}
public static class Point {
private int x;
private int y;
/**
* The main constructor of Point Class, used to represent the 2 Dimension points.
*
* @param x the point's x-value.
* @param y the point's y-value.
*/
public Point(int x, int y) {
this.x = x;
this.y = y;
}
/**
* @return x, the x-value
*/
public int getX() {
return x;
}
/**
* @return y, the y-value
*/
public int getY() {
return y;
}
/**
* Based on the skyline theory,
* it checks if the point that calls the function dominates the argument point.
*
* @param p1 the point that is compared
* @return true if the point wich calls the function dominates p1
* false otherwise.
*/
public boolean dominates(Point p1) {
// checks if p1 is dominated
return (this.x < p1.x && this.y <= p1.y) || (this.x <= p1.x && this.y < p1.y);
}
}
/**
* It is used to compare the 2 Dimension points,
* based on their x-values, in order get sorted later.
*/
class XComparator implements Comparator<Point> {
@Override
public int compare(Point a, Point b) {
return Integer.compare(a.x, b.x);
}
}
}
