Finding "entrance" points in a set of d-dimensional points. Can I do better than O(N^2)?

Question

I am given a set of d-dimensional points, and need to find the set of entrance points in them.

Definitions:

• A point p1 captures p2 if 1) All dimensions of p1 is smaller or equal to p2; and 2) At least one dimension of p1 is strictly less than its corresponding dimension of p2. (e.g. p1 = <1.0, 2.0, 3.0>, p2 = <1.0, 3.0, 3.0>, since 1.0 == 1.0, 2.0 < 3.0, 3.0 == 3.0, we say p1 captures p2.
• An entrance point is a point which it is not captured by any other points in the dataset.

For example, in the following dataset:

n = 4, d = 2
=============
p1 = <0.3, 1.5>
p2 = <0.2, 1.4>
p3 = <0.1, 1.7>
p4 = <0.8, 0.9>

The entrance points are {p2, p3, p4} because:

1. p1 is captured by p2 because all dimensions of p2 is less than p1.
2. p2, p3, p4 cannot capture each other.

---

Assuming d is a constant. Now I can only think of a naive O(N^2) solution, that is, take every possible pair of the points and compare the dimensions one by one. If a point is captured by the other, eliminate it from the final set.

I also thought of a divide-and-conquer solution. That is, recursively break the points down into two partitions, perform the previous O(N^2) algorithm to eliminate some candidates from the final set, then recursively merge each pair of the partitions, say part1 and part2, back by comparing each possible pair of points one from part1 and one from part2. However, even though the running time is a little faster with the aid of multi-threading, I found that it is still an O(N^2) algorithm because T(N)=2T(N/2)+O(N^2) ==> O(T(N)) = O(N^2).

I wonder if there exists an algorithm with lower time-complexity for this problem.

Also, is there any well-known name for this problem? Or are there any well-known problems similar to this one so I can look into?

Answer 1

Your problem is similar to finding Maxima of a point set in a $d$-dimensional space. In $2$-$D$ and $3$-$D$ there is a simple Divide and Conquer algorithm that has a $O(n \log n)$ running time. For higher dimension, there is $O(n (\log n)^{d-3}\log \log n)$ time algorithm as given in the Wikipedia page.

You can covert your problem to the Maxima problem, by simply negating the coordinate values of the input points. In other words, your problem is a Minima problem.