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
    @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