0
$\begingroup$

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 ?

$\endgroup$
  • 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$ – greybeard Apr 23 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. Apr 24 at 18:18
  • $\begingroup$ Updated the question. $\endgroup$ – Arkaprava Paul Apr 25 at 12:47
1
$\begingroup$

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)$.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ What if we presort the points in order of the x-ordinates in ascending order ? $\endgroup$ – Arkaprava Paul Apr 26 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. Apr 27 at 4:17
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Been there, done that more than one third of a century ago. $\endgroup$ – greybeard Apr 28 at 20:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.