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
    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.2012-12-30
  • 0
    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 known2012-12-30
  • 3
    We need information regarding the red points.2012-12-30
  • 0
    For example in the figure above, from left to right, r1=-2.5, r2=0.5, and r3=3. the solution is x=-0.52012-12-30
  • 0
    If the segments overlap, how can i find the nearest point (on left or right)?2012-12-30
  • 0
    For each red point $r_i$, consider the points on left and right: $r_i\pm 1$.2012-12-30
  • 0
    I think there can be an algorithm for this process. I am trying to think of how to write it in mathematical language, however.2012-12-30
  • 0
    I have about n=10000 such red points. your algorithm requires about O(n^2). If a more scalable solution exists?2012-12-30
  • 0
    remo, what do you think of my algorithm?2012-12-30
  • 0
    I must check both sides of every red point and check if it is within another red segment or not. Do you think if any preprocessing may improve it?2012-12-30
  • 1
    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.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
    No it doesn't. It requires $O(n\log n)$ for sorting, and the rest is $O(n)$.2012-12-30
  • 0
    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?2012-12-30
  • 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}$.