Skip to main content
deleted 3 characters in body
Source Link
Inuyasha Yagami
  • 6.3k
  • 1
  • 12
  • 23

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 by negating the coordinate values of the input points. In other words, your problem is a Minima problem.

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 by negating the coordinate values of the input points. In other words, your problem is a Minima problem.

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.

Source Link
Inuyasha Yagami
  • 6.3k
  • 1
  • 12
  • 23

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 by negating the coordinate values of the input points. In other words, your problem is a Minima problem.