1
$\begingroup$

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

enter image description here

  • 1
    I do not understand the co$m$putational co$m$plexity notion of this question, so I cannot co$m$ment on that. I do hope that my answer is of some help, though.2012-12-30

3 Answers 3

3

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; if not, write down "$\color{blue}{p_0+1), (p_1-1,}$". Check if $p_2-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.

  • 0
    +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.2012-12-31
3

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.

3

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