Search for a set of horizons

Question

Let me explain some definition before moving on to the problem:

Let's say point A is the coordinates (which can have a double value), say (1,2,3,5,4,3,2,6), the same as point B.

Point A dominates point B, if and only if 1. all coordinates at point A <= all coordinates at point B and 2. one coordinate of point A <corresponding coordinates of point B

For example: Given

A=(2,3,4,5) B=(2,3,4,6) 

A dominates B, since condition 1 is satisfied, and for condition 2, the fourth component A <the fourth component B.

Given another example,

 A=(2,3,4,5) B=(2,3,4,5) 

Neither A dominates B, and vice versa, since condition 2 is not satisfied in both cases.

Now, given the list of n-dimensional coordinates, I want to find a set of coordinates that others don't dominate, these coordinates are called horizon settings.

Say I have coordinates in 5 dimensions

 (2,1,2,1,2) (1,2,1,2,1) (3,3,3,3,3) (4,4,4,4,4) 

Set horizon

 (2,1,2,1,2) (1,2,1,2,1) 

Now I want to write a function:

 List<double[]> SkylineSet(List<double[]> Coordinates, int dimension) 

This example input:

  List<double[]> newList=new List<double[]>(); newList.Add(new double[] {2, 1, 2, 1, 2}); newList.Add(new double[] { 1, 2, 1, 2, 1 }); newList.Add(new double[] { 3, 3, 3, 3, 3 }); newList.Add(new double[] { 4, 4, 4, 4, 4 }); 

SkylineSet(newList,5) prints

 (2,1,2,1,2) (1,2,1,2,1) 

This can be achieved by comparing each coordinate, but the number of coordinates can be very large, anyone has an idea how to solve this problem effectively?

Answer 1

Place the dots in the KD tree (or some such data structure). Now you can effectively find the points at which the given point dominates. Remove those that dominated, repeat all remaining points.

Answer 2

I'm not sure if this will work. It seems believable in my head. It is also possible that this is exactly what you are already doing.

Build the dominance matrix NxN, where N is the number of points. The values ​​in the matrix are “equal”, “dominate”, “dominate”, “neither”. Set all matrix cells equal. This matrix contains the result at the end of the algorithm.

Start with the first coordinate.

I assume that we have one array with all the values ​​of the current coordinates, but also at what point they belong.

Establish a partial dominance relationship by looking only at the current coordinate. The dominance relation can have one of these meanings: “equal”, “dominated”, “dominant”. There is no "neither".

Skip this array in a double nested loop (I = 0, N-2; J = i + 1, N-1). Given the ratio R of two points and cell C in the relationship matrix for these two points, update the matrix to the new C values ​​as follows:

If C was "equal," then C = R.
If C was not “neither,” then it has not changed.
If C was “dominated” and R “dominated”, then C becomes “not a single one”, otherwise it does not change.
If C "dominates" and R "dominates", then C becomes "not a single one", otherwise it remains unchanged.

Repeat the process for all coordinates, copying the results in the matrix.

At the end, run the matrix for each point. Take all points that do not have a “dominant” relationship with any other point.