2
$\begingroup$

This problem is a by product of another problem. I would like to restate this problem as a sort of a puzzle.

Suppose we have a $l \times b$ grid. We select $k$ points on the grid randomly and independently assuming all points selected are distinct. That is $k$ distinct points on the grid are selected. The distance between two points is the euclidean distance between them. We are given a rope of length $n$. We want to connect all the points on the grid using this rope.

It can be noticed that this problem is similar to spanning tree problem. But we are allowed to cut the rope and tie the rope to the middle of another rope. For example below.

           o Node1
           |
           |

Node3 o-------------------------o Node2

The problem statement is, we just want to ensure all nodes are connected to each other.

It can be noted that for a given $k, n, l, b$ there exists probability that the nodes can be connected. For larger $l, b$ the probability is small and for smaller $l,b$ the probability that they can be connected is large.

Can we find a relation?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ I think you're asking for $P(k,n,l,b)$, the probability that you can connect all the points, maybe you could confirm this. Also I think the keyphrase you're looking for is "Steiner tree." Must all the rope bits run along gridlines? This, too, should be clarified. $\endgroup$
    – Gerry Myerson
    Commented Apr 5, 2011 at 6:29
  • $\begingroup$ Yes $P(k,n,l,b)$ is the probability I am looking for. The rope may or may not run along grid lines. I think it might be easier to consider that it does not run along grid lines. However the original problem I have in mind does require the rope be along grid lines. But if the problem can be solved as $L_{2}$ norm distances then $L_{1}$ norm probability will be higher! How does Steiner tree fit here? $\endgroup$
    – SpringCoder
    Commented Apr 5, 2011 at 9:00
  • $\begingroup$ @SpringCoder, did you look to see what a Steiner tree is? $\endgroup$
    – Gerry Myerson
    Commented Apr 5, 2011 at 13:16
  • $\begingroup$ @Gery: Yes, I suddenly forgot the definition and went back to check it..you have pointed in the right direction. Thanks a lot. I am trying to see how the $l,b$ parameters can now fit in! $\endgroup$
    – SpringCoder
    Commented Apr 5, 2011 at 13:23

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .