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?

  • 0
    What is a connected point?2011-02-06
  • 0
    @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$.2011-02-06
  • 0
    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."2011-02-06
  • 0
    @Qiaochu: "There is no such thing..." only if you consider a finite set of points. An infinite lattice is evenly distributed over an infinite plane in some sense. Another possibility is that one can imagine the points coming from a two-dimensional Poisson process.2011-02-06
  • 1
    @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](http://en.wikipedia.org/wiki/Graph_%28mathematics%29) 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.2011-02-06
  • 0
    @Rahul: yes, but it's far from _randomly_ distributed.2011-02-06
  • 0
    @Qiaochu: Yes, that's why I also mentioned a two-dimensional Poisson process, which *is* random.2011-02-06
  • 0
    @Rahul: I've updated the question with an image and further description. Hope it clarifies some things.2011-02-07
  • 2
    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.2011-02-07
  • 0
    @mjqxxxx: Within a certain precision, there would be. It's discrete. Probably should've noted that, otherwise the number of congruent subsets is either infinite or zero, depending on how you like to interpret the relationship between the infinite plane and the zero probability of congruence. ;)2011-02-07
  • 0
    @Qiaochu: Pick some large circle and throw in points u.a.r. such that the expected distance is $k$; now hope that the expected distance the question asks for tends to a limit as the radius of the circle grows.2011-02-07
  • 0
    @Jon: If you reframe the question to be about the distance to a subgraph that is the same "within a certain precision," there will be a non-trivial answer (which will presumably depend on the precision). You would also need to specify where the underlying graph is coming from. Some comments have suggested that a Poisson process is appropriate for generating the points. Where do the edges come from? Is the graph the Delaunay triangulation, or the relative neighborhood graph, or what?2011-02-07

0 Answers 0