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