Take the 2-minute tour ×

I am trying to create a triangular grid/mesh for a rectangular domain in $\mathbb{R}^2$ with the property that each vertex is shared by (at most) four edges. Is this possible to accomplish?

share|improve this question
Finite or infinite? –  Brendan McKay Aug 21 '12 at 14:04
As long as you do not need more than 8 regions. Gerhard "Otherwise You Need Different Geometry" Paseman, 2012.08.21 –  Gerhard Paseman Aug 21 '12 at 14:59
I can only see how to do $6$ regions. An octahedron is a closed manifold. –  Will Sawin Aug 21 '12 at 17:46

2 Answers 2

Since there is no requirement that the outer region must be a triangle, the question is not quite as trivial as indicated in earlier comments. The rectangle $[0,n] \times [0,1]$ can be triangulated by dividing it into unit squares and then inserting the SW-NE diagonal in each square. Still, this might not be the kind of grid/mesh one wants. To see the problem, it might be easier to think in terms of angles than to use Euler's polyhedron formula: If there are interior points in the triangulation, then the angles at those points have to be at least $90^\circ$ on average, while the average angle in a triangle is only $60^\circ$. It follows that most vertices of the triangulation have to be on the boundary of the region.

share|improve this answer
How is your suggestion a triangulation? Is it for only some pairs (a,b)? When I try it I get quadrilaterals. Gerhard "Maybe This Is Different Geometry" Paseman, 2012.08.21 –  Gerhard Paseman Aug 21 '12 at 19:04
Actually I try it and I see more triangles, but also degree 6 vertices. I must be doing something wrong. Gerhard "A Picture Would Really Help" Paseman, 2012.08.21 –  Gerhard Paseman Aug 21 '12 at 19:05
Gerhard, maybe I was a bit sloppy, answer edited. –  Johan Wästlund Aug 21 '12 at 19:20
OK,now I understand your edited version. Have you any triangulations with more than 3 vertices in the interior? My guess is that even one vertex in the interior seriously limits the possibilities. Gerhard "Ask Me About System Design" Paseman, 2012.08.21 –  Gerhard Paseman Aug 21 '12 at 19:24

This question is too elementary for MO, but here's a hint. (See the FAQ for alternative sites to ask your question.)

  1. Familiarize yourself with the notion of Euler characteristic

  2. Convince yourself that the Euler characteristic of your triangulation of a rectangle is 1.

  3. Deduce some inequalities on the numbers of vertices, edges and faces, assuming all faces are triangles and all vertex valences are less than or equal to 4.

share|improve this answer

Your Answer


