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?

  • 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 Apr 5 '11 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 Apr 5 '11 at 9:00
  • $\begingroup$ @SpringCoder, did you look to see what a Steiner tree is? $\endgroup$ – Gerry Myerson Apr 5 '11 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 Apr 5 '11 at 13:23

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.