Given a set of points $P=p_1,p_2,..p_n$ in $R^2$ in where $p_i=(x_i,y_i)$,finding the point with smallest x-ordinate having y-ordinates between $y_1$ and $y_2$, where $y_1$ and $y_2$ are given as inputs. I can compare the point with other points which gives me an $O(n)$ time algorithm ? Can this be improved any further ?
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ In a simple list ordered from left to right, I can find the leftmost in $O(1)$: specify what is represented how. $\endgroup$– greybeardCommented Apr 23, 2020 at 5:04
-
$\begingroup$ The answer depends on how the input (the list of points) is represented, and can't be answered without that information. If you'd like your question to be answered, please edit it to provide the requested information. Also, when you say $O(n)$, $O(n)$ what? $O(n)$ time? $O(n)$ comparisons? $\endgroup$– D.W. ♦Commented Apr 24, 2020 at 18:18
-
$\begingroup$ Updated the question. $\endgroup$– Arkaprava PaulCommented Apr 25, 2020 at 12:47
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
Not unless you assume something more. Without further assumptions, if you don't check all $n$ values, the minimum can be some of the unchecked points.
If you know there is just one minimum in (sorted) range, a variant of binary search (the minimum is the point where $x_{k - 1} > x_k < x_{k + 1}$ or one of the endpoints; if $x_k > x_{k + 1}$ the minimum is to the right, and so on) gets it in time $O(\log n)$.
$\begingroup$
$\endgroup$
2
If the points are provided in an arbitrary order (not sorted or anything), then no, you cannot do better than $O(n)$ time. You must examine every point. This is easily proven using an adversary argument: if there is any point your algorithm doesn't inspect, then that point could have had a valid $y$-value and a smaller $x$-value than whatever your algorithm outputs, meaning that any such algorithm will have inputs on which it outputs the wrong answer.
-
$\begingroup$ What if we presort the points in order of the x-ordinates in ascending order ? $\endgroup$ Commented Apr 26, 2020 at 21:21
-
$\begingroup$ @ArkapravaPaul, I can only answer the question that was asked, and that is not part of the problem specification in the answer. I believe you should be able to figure out the answer to that variant as well on your own: try adapting the ideas in my answer. What's the fastest algorithm you can find? Can you come up with an adversary argument? $\endgroup$– D.W. ♦Commented Apr 27, 2020 at 4:17
$\begingroup$
$\endgroup$
1
A Computational Geometry answer would include a description of a data structure and analysed algorithms for preprocessing/set-up and queries.
There is Edward McCreight's Priority Search Tree, use a min heap on $x$ with $y$ medians for telling left from right. (The first point you encounter between $y_1$ and $y_2$ is the one with the lowest $x$ in range.)
Not storing the additional median in each node, but using the point's coordinate works almost as well for well behaved sets.
-
$\begingroup$ Been there, done that more than one third of a century ago. $\endgroup$ Commented Apr 28, 2020 at 20:57