Timeline for A disc contains many random points. Each point is connected to its nearest neighbor. What is the expectation of average cluster size?
Current License: CC BY-SA 4.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 22 at 13:29 | vote | accept | Dan | ||
| Jan 16 at 12:18 | comment | added | Timothy Chow | @DanielAsimov Suppose no two points are exactly the same distance apart. Then we have a directed graph in which every vertex has outdegree one, so each connected component of the underlying undirected graph is unicyclic (the cycle might have just 1 or 2 vertices). In such a component, consider the pair of points that are closest together; they must form a cycle of length 2. But in the underlying undirected graph, a cycle of length 2 manifests itself as a single undirected edge. | |
| Jan 16 at 5:34 | history | became hot network question | |||
| Jan 16 at 3:39 | comment | added | Dan | @JamesMartin That seems right to me. I have written your comment as an answer. | |
| Jan 16 at 3:38 | answer | added | Dan | timeline score: 12 | |
| Jan 16 at 2:08 | comment | added | James Martin | @DanielAsimov The description doesn't specify what happens if there is a point with two equally near nearest neighbours. But anyway, if the points are uniformly distributed in continuous space, the probability of that happening is $0$. | |
| Jan 16 at 2:08 | history | edited | Daniel Asimov | CC BY-SA 4.0 |
[In title:] uniform random —> uniformly distributed
|
| Jan 16 at 2:06 | comment | added | Daniel Asimov | What graph is it that has no cycles? If the points in the disk are all vertices of a fixed regular polygon, won't the nearest neighbor graph have a cycle (and only one component)? | |
| Jan 16 at 0:16 | comment | added | James Martin | The graph has no cycles, so the number of components is $n$ minus the number of edges, which is equal to the number of pairs which are mutually nearest neighbours. As $n\to\infty$, what you see locally around a typical point looks like a Poisson process. So the average number of clusters per point tends to $q_2/2$, where $q_2$ is the probability for a typical point in a 2-dimensional Poisson process to be in a mutually-nearest-neighbour pair. But isn't that already what's calculated by joriki in the "Stars in the universe" question you linked to?: $q_2/2\approx0.31075$. What am I missing...? | |
| Jan 15 at 23:03 | comment | added | Dan | @YCor Thanks, I have changed it to disc. | |
| Jan 15 at 23:02 | history | edited | Dan | CC BY-SA 4.0 |
deleted 2 characters in body; edited title
|
| Jan 15 at 22:57 | comment | added | YCor | The points are on the disc, not on the circle. | |
| Jan 15 at 21:34 | history | asked | Dan | CC BY-SA 4.0 |