Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?
share|improve this question
    
Your related question is not going to work for a finite number of "randomly deployed points" –  Henry Oct 14 '11 at 11:18
    
No, of course. The number of deployed points will be infinite. –  ght Oct 14 '11 at 11:23

1 Answer 1

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

share|improve this answer
    
Jim, thanks for answering my question! It makes a lot of sense. Actually, what I would really like to do is the following. Consider a density in the Euclidean space and randomly deploy points accordingly to this density. Now construct the associated Delaunay triangulation. Does there exists a density whose average degree distribution is greater or equal than 7? I will edit my question to include this but your answered my original question perfectly! –  ght Oct 13 '11 at 23:24
    
These images of hyperbolic tesselations are relevant, especially this one. –  joriki Oct 13 '11 at 23:45
    
@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. –  Grumpy Parsnip Oct 14 '11 at 0:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.