If there are $N$ people on the positive $x$-axis and one man can send a message to another one only if the distance between them is $\leq k $.

Question

The question is how to determine a function which would decide if a pair of persons can communicate with each other, where communication is possible only if the distance between two individuals are less than $k$ units apart. For example:

If following are the coordinates in which the people reside on the $x$-axis:

$10$, $13$, $18$, $15$, $33$, and value of $k$ is $3$.

Then $10$ and $13$ can communicate, and $13$ and $18$ can't communicate directly but $13$ to $15$ and $15$ to $18$ is possible, hence $13$ and $18$ can communicate. But, $33$ can't communicate with any person.

How would one design a function which determines if communication is possible between a pair of persons?

Answer 1

If the coordinates are $a_1 < a_2 < \cdots < a_n$, then $a_i$ can communicate with $a_j\ (i < j)$ iff $$f(a_i,a_{i+1}) \cap f(a_{i+1},a_{i+2})\cap \cdots \cap f(a_{j-1},a_{j}) $$ where $f(x,y)$ is $True$ if $x$ can communicate with $y$, else $False$. So a function that does what you want, for input coordinates $x$ and $y$, is given by the formula

$$\bigcap_{m=i}^{j-1} f(a_m,a_{m+1}) $$ where $a_i = \min(x,y)$ and $a_j = \max(x,y)$.

E.g., implemented in Sage:

def g(x,y,L,k):
    x,y = min(x,y),max(x,y)
    L = sorted(L) 
    i = L.index(x)
    j = L.index(y)
    return prod([(L[m+1]-L[m] <= k) for m in [i..j-1]])

where x,y are the coordinates to test, L is the list of coordinates, and k is the distance criterion.

Answer 2

You have an undirected graph whose vertices are the coordinates of the people, with an edge between two vertices if they are $\le k$ units apart, and you wish to determine what the connected components are in the graph. There are reasonably efficient algorithms either to find connected components or to find the connected component of a given vertex (i.e., to determine who a given person can communicate with). See for example http://en.wikipedia.org/wiki/Connectivity_(graph_theory)

Answer 3

Let the $N$ people be an positions $x_1, x_2, \dots, x_N$. Then find $$A= \bigcup_{i=1}^N [x_i - k, x_i + k]$$ and if $A$ is connected everyone can communicate. More generally a person can only communicate with others in the same connected component of $A$.