16
$\begingroup$

Assume you have a Poisson point process of constant intensity $\lambda$ in the Euclidean plane. From this point process we construct the Delaunay triangulation (or the Voronoi tessellation for that matter).

It is known [Stoyan et all] that the expected degree of a typical vertex has degree 6. Moreover, there are several results for the average area of a typical triangle, edge lengths and so on. However, all the results seem to be for constant intensity. My question is: Is it known how the expected degree changes as we change the intensity?

More specifically, assume we have a rotationally invariant intensity $\rho(r)$ where $r$ is the distance to the origin and assume that $\rho(r)\to\infty$ as $r$ increases. How, does the expected degree of a node depends on its distance to the origin. The intuition is that the degree is going to increase as $r$ increases but is there any known result or reference in this direction? This is not my research area so I will appreciate any help or comment!

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Two naive comments. 1) The proof that the expected degree of a typical vertex has degree 6 is not difficult (if I remember correctly, apart from boundary terms, this is just a combinatorial result). So maybe it would not be that difficult to adapt the proof if this is possible. 2) Could it be related to Delaunay triangulation on hyperbolic spaces ? There may be a few results on it $\endgroup$
    – camomille
    Commented Mar 25, 2011 at 23:49
  • 2
    $\begingroup$ @Camomille: Thanks for your comment. You raised a very good question. I don't know what is the expected degree for the Delaunay triangulation on the hyperbolic space but I guess there should be some results there...anyone knows? $\endgroup$
    – ght
    Commented Mar 26, 2011 at 0:56

3 Answers 3

Reset to default
6
$\begingroup$

The expected degree for the Delaunay triangulation on hyperbolic space will depend on the density of the points. With low enough density points, you should get arbitrarily high degree. You should be able to get the expected degree as high as you want for a point distribution in the plane by taking the conformal representation of the hyperbolic plane as a varying metric in a unit disc (the Poincare disc), and placing the points with density proportional to this metric. Then the density goes to infinity at the boundary of the circle.

Note that since the Poincare disc model takes circles in the hyperbolic plane to circles in the disc, the Delaunay triangulation of a set of points (which is characterized by the fact that the circumcircle of every triangle does not contain another point) is the same in the disc and the hyperbolic plane. Thus, the expected average degree of the Delaunay triangulation should be the same in both of these scenarios.

The above construction satisfies the conditions stated in your question, but I don't know if you'll be satisfied. Did you want the points to be distributed on the entire plane? If so, I expect it's impossible because there's no way to put a conformal metric on all of $\mathbb{R}^2$ that gives the hyperbolic plane (although note that this isn't quite a proof).

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ @Shor: Thank you for your comment. I didn't follow why did you say that for low enough density points, I should get arbitrary large degree. It seems to me that the bigger the density the higher the average degree. More precisely, if the density is rotationally invariant and increases as $r\to 1$ (the boundary of the Poincare disk) then the average degree of nodes in the annulus $A(r,r+dr):=\{x\in\mathbb{D}:r\leq |x|\leq r+dr\}$ should also increase. Isn't this right? Your are absolutely right that the problem in $\mathbb{R}^2$ and the hyperbolic disk are quiet different. $\endgroup$
    – ght
    Commented Mar 26, 2011 at 13:07
  • $\begingroup$ I mean the density in the hyperbolic plane. If you look at a small region of the hyperbolic plane, it looks a lot like the Euclidean plane, and the average degree will only be slightly more than 6. If you look at a large region of the hyperbolic plane, it looks very different from the Euclidean plane, and the average degree will be a lot more than 6. In the Euclidean plane, the average degree is determined not by the density, but by something like the rate of change of the density. $\endgroup$
    – Peter Shor
    Commented Mar 26, 2011 at 13:54
  • $\begingroup$ I'm confused by your remark that "there's no way to put a metric on all of $\mathbb R^2$ that gives the hyperbolic plane." Did you mean for the word "conformal" to be in there somewhere? $\endgroup$
    – Kevin Walker
    Commented Mar 26, 2011 at 15:16
  • $\begingroup$ @Kevin: Yes, "conformal" should have been in there. And for this question, we could add "rotationally invariant" as well, which I suspect leaves the Poincare metric as the only example. Thanks $\endgroup$
    – Peter Shor
    Commented Mar 26, 2011 at 16:58
9
$\begingroup$

Let's speak momentarily about the space average, rather than the expected degree. That is, consider the (expectation of the) average degree over all vertices in the disc of radius $R$ around the origin and take $R$ to infinity. I claim that unless the intensity increases really fast (exponentially?) this average will stay 6.

The reason is that any simple finite planar graph has average degree less than 6. Hence, if the ball (in the graph metric) of radius $n$ in a planar graph has average degree, say, 7 then the size of the boundary of that ball is some constant fraction of the size of the ball and this holds for any $n$, thus requiring exponential growth (in the graph metric). I have not checked it, but it seems that this implies exponential growth of the density function, and perhaps much more than this. Actually, right now I'm not sure whether you can get average degree 7 with any $\rho$ that does not blow to infinity in a finite radius (but maybe it's trivial in one way or another - it's late).

As a side note, $\rho$ being monotone is not enough to guarantee that the expected degree is monotone. Since the expected degree is 6 for any constant density, if the density is almost constant in some large region then the expected degree there is roughly 6 in that region.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ @ Ori: did you mean to say that "...any simple finite planar graph has average degree less than 6"? This is clearly not true! $\endgroup$
    – ght
    Commented Mar 26, 2011 at 12:44
  • 2
    $\begingroup$ I did mean that - it's a classic. The key word here is "simple" - no loops or multiple edges. Assume the graph is a triangulation (otherwise add edges). Then use Eular's formula + 2E=3F to get a bound on 2E/V which is the average degree. $\endgroup$
    – Ori Gurel-Gurevich
    Commented Mar 26, 2011 at 15:04
0
$\begingroup$

There are also articles available online, that are related to that topic:

http://www.ics.uci.edu/~eppstein/pubs/BerEppYao-IJCGA-91.pdf

http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=879ADD299F6B2BF663BAA98F334D30A1?doi=10.1.1.40.1419&rep=rep1&type=pdf

and a lot more are reported when feeding "distribution of vertex degrees in triangulations" into a popular search engine.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .