1
$\begingroup$

I was doing some thought experiments for a game project, and while considering something related to pathfinding, this problem came into my head.

Say we have an infinite plane that is covered with an even random distribution of connected points, such that the average distance of a point to any of its connected neighbours is some constant $k$. Given an arbitrary subset of these points of size $n$, is it possible to say anything about the average distance $d$ to the nearest of the infinite number of congruent subsets elsewhere in the plane?

Example:

Graph Example

It's basically a graph embedded in the plane with non-intersecting edges. For the purpose of the problem, I can assume that it always subdivides the plane into triangles. The average distance between $v$ and its 6 neighbours is approximately $k$. The subset $S$ of size $n=3$ is congruent to the subset $S'$, and the subset $T$ of size $n=2$ is congruent to the subset $T'$. It's not shown here, but a subset need not be fully connected: you could have a subset $R=S \cup T$, for instance, to which $S' \cup T'$ is not congruent. Because the plane is infinite, for any given subset there are infinitely many congruent subsets. Since subsets of size 1 are an average of $k$ units away from the nearest congruent subset, is the average distance between congruent subsets proportional to $n$, and if so, how so?

$\endgroup$
12
  • $\begingroup$ What is a connected point? $\endgroup$
    – Qiaochu Yuan
    Commented Feb 6, 2011 at 20:30
  • $\begingroup$ @Qiaochu Yuan: Sorry, I didn't really know how to word it. For each point, there is a set of line segments connecting it to all nearby points, and the average length of these segments is $k$. $\endgroup$
    – Jon Purdy
    Commented Feb 6, 2011 at 20:34
  • $\begingroup$ This question is not really well-defined. There is no such thing as a collection of points evenly distributed over an infinite plane, since by symmetry the probability that the points are in any given coordinate square is zero. You should either restrict to a finite square (so you will also have to restrict to a finite set of points) or change the distribution (e.g. make it Gaussian centered at the origin). I also don't know what you mean by "infinite number of congruent subsets elsewhere in the plane." $\endgroup$
    – Qiaochu Yuan
    Commented Feb 6, 2011 at 20:37
  • 1
    $\begingroup$ @Jon: Perhaps if you could draw a crude picture of what you are thinking of, it might help us understand. This sounds like a graph with an infinite number of vertices embedded in the plane, but it is not clear how many edges each vertex has, whether edges can intersect, what you mean by a congruent subset, and so on. $\endgroup$
    – user856
    Commented Feb 6, 2011 at 21:17
  • 2
    $\begingroup$ Why would there ever be a congruent subset? If you choose points $x_1, x_2, ...$ from the uniform random distribution on $[0, 1]$, the probability that any two are exactly equal is 0. $\endgroup$
    – mjqxxxx
    Commented Feb 7, 2011 at 2:38

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .