# How to find the best point?

I want to find x in the figure below where it must be as close as possible to 0, but not near to red points (the minimum distance of x to each red point must be at least 1).

• But the figure does not show the distance between the red segments. If the distance to a red point (not to any point on the red segments) must be at least $1$ you have to options: one on the left and other on the right. Then you choose the nearest one. Commented Dec 30, 2012 at 17:06
• The distance between red segments is not important, I want the green point be out of the red segments but as close as possible to the origin. All red points are given and known
– remo
Commented Dec 30, 2012 at 17:11
• We need information regarding the red points.
– 000
Commented Dec 30, 2012 at 17:11
• For example in the figure above, from left to right, r1=-2.5, r2=0.5, and r3=3. the solution is x=-0.5
– remo
Commented Dec 30, 2012 at 17:12
• I do not understand the computational complexity notion of this question, so I cannot comment on that. I do hope that my answer is of some help, though.
– 000
Commented Dec 30, 2012 at 17:41

Sort the points in increasing order. Build a set of disjoint intervals by walking along the sorted points, merging intervals corresponding to points within a distance of $2$. After that, it should be easy because you have a sorted set of disjoint intervals which you can walk down without worrying about overlaps.

In more detail: Suppose $p_1, p_2, \ldots, p_n$ are in increasing order. Write down "$\color{blue}{(p_1-1,}$". Check if $p_1-1<p_0+1$; if not, write down "$\color{blue}{p_0+1), (p_1-1,}$". Check if $p_2-1<p_1+1$; if not, write down "$\color{blue}{p_1+1),(p_2-1,}$". And so on... In the end, write down "$\color{blue}{p_n+1)}$". You will have written down the collection of disjoint intervals formed by the union of the $(p_i-1, p_i+1)$. Turning this into (pseudo)code is left as an exercise for the reader.

• No it doesn't. It requires $O(n\log n)$ for sorting, and the rest is $O(n)$.
– user856
Commented Dec 30, 2012 at 17:36
• Seeing the other answers, I see that finding the full set of disjoint intervals is overkill for this particular problem. Oh well. Edit: @remo, shouldn't you accept Karolis's or hardmath's answers?
– user856
Commented Dec 30, 2012 at 17:49
• +1 I think Rahul's approach is nice in clarifying what needs to be done. With a minor change, it is equivalent to the solution Karolis and I suggest, namely stopping when the (connected) interval containing zero (if any) cannot be further extended. Commented Dec 31, 2012 at 15:50

Given an array of red points. First sort it. Then, use binary search to find the $i$ such that $r_i$ is closest to $0$. If $|r_i| \geq 1$ you are done. Else, consider point $r_i - 1$. If it is inside $r_{i-1}$, next consider the point $r_{i-1} -1$ continue this way until some $r_k -1$ is not inside $r_{k-1}$. Do the same for $r_i + 1$, $r_{i+1} + 1$ until $r_j + 1$ is not inside $r_{j+1}$. In fact, you could go left and right in parallel for a slight optimization. Finally pick the smaller of $r_k-1$ and $r_j +1$ - that's the answer you want.

Note this algorithm takes constant space (assuming sorting happens in place) and will most often only process a small number of $r_i$ points.

Sort $R$ into "red points" ascending above the origin $R_+$ and descending below the origin $R_-$. Test the sorted lists $R_+,R_-$ to find the least feasible value $x \ge 0$, resp. the greatest feasible value $y \le 0$. If there are $n$ red points, sorting takes $O(n \log n)$ time, which dominates the final search for feasible $x,y$. Compare $x,y$ and choose the one closest to the origin.

Actually the searches for $x,y$ can be interlaced and early terminated as soon as one or the other is found to be closest to the origin.

Details of search:

For simplicity we sketch the searches for "candidates" $x_{can} \ge 0$ and $y_{can} \le 0$ for the nonnegative and nonpositive feasible values closest to the origin without interlacing the two searches, relying on a final comparison to determine which is closest. This doesn't affect the overall complexity.

Let the sorting result in finite lists $R_+ = [x_1,x_2,\ldots,x_p]$ ascending and $R_- = [y_1,y_2,\ldots,y_q]$ descending, with $p=0$ or $q=0$ respectively if one or the other list proves empty.

If $0 \in R$ $\{x_{can} := 1 \;; y_{can} := -1\}$; else $\{x_{can} := \max(0,y_1+1) \;; y_{can} := \min(0,x_1-1)\}$.

Set $i := 1$ and $j := 1$.

While $(i \le p$ and $x_{can} \gt x_i - 1)$ $\{x_{can} := x_i + 1 \;;\; i := i+1\}$.

While $(j \le q$ and $y_{can} \lt y_j + 1)$ $\{y_{can} := y_j - 1 \;;\; j := j+1\}$.

If $(x_{can} + y_{can} \le 0)$ return $x_{can}$; else return $y_{can}$.