3
$\begingroup$

I have a couple of questions about triangulations of the Euclidean space:

  • Is it possible to have an infinite triangulation of the Euclidean space $\mathbb{R}^2$ such that only a finite number of vertices have degree less or equal than 6?

  • If not, is it possible to have a triangulation where the average degree is greater or equal than 7? Here by average degree I mean the limit in $r$ of the average degree of all the points in the ball of center the origin and radius $r$.

Thanks!



Jim below answered my question with a nice example! Now I have a follow up related question:

  • Consider a density in the Euclidean space and randomly deploy points accordingly to this density. Now generate the corresponding Delaunay triangulation. Does there exists a density whose average degree is greater or equal than 7 almost surely?
  • 0
    No, of course. The number of deployed points will be infinite.2011-10-14

1 Answers 1

5

Sure it's possible. You can make it have constant valence of any degree $n$ higher than $6$. Here's one construction. Take a circle, call it $C_1$, and $n$ points on this circle. Connect the center to each of these points. So the center now has valence $n$ and all the points have valence $3$. So now take a larger circle, $C_2$, around this first one. Scatter points on this larger circle so that there are $n-3$ edges coming out from each point on $C_1$ and hitting $C_2$ in distinct points, except that the outermost edges from neighboring points on $C_1$ have to connect to the same point on $C_2$ to get a triangulation. This yields points on $C_2$ of valences $3$ and $4$. Now repeat this process with a new circle $C_3$, and proceed ad infinitum. Here is a picture of the first $3$ stages when $n=7$. As you can see, the triangles are getting scrunched together as you move outwards. This is because this is really a triangulation of the hyperbolic plane, so you have to fit a lot of area (assuming all triangles are the same size) into a small Euclidean area. enter image description here

  • 0
    @ght: I think you can do that if you choose a homeomorphism to the hyperbolic plane, and pull back the hyperbolic area form to $\mathbb R^2$. Then sprinkle your points according to that density. So it will be getting denser from the Euclidean perspective as you move outward.2011-10-14