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?
-
$\begingroup$ Finite or infinite? $\endgroup$– Brendan McKayAug 21, 2012 at 14:04
-
$\begingroup$ As long as you do not need more than 8 regions. Gerhard "Otherwise You Need Different Geometry" Paseman, 2012.08.21 $\endgroup$– Gerhard PasemanAug 21, 2012 at 14:59
-
1$\begingroup$ I can only see how to do $6$ regions. An octahedron is a closed manifold. $\endgroup$– Will SawinAug 21, 2012 at 17:46
2 Answers
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.
-
$\begingroup$ 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 $\endgroup$ Aug 21, 2012 at 19:04
-
$\begingroup$ 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 $\endgroup$ Aug 21, 2012 at 19:05
-
$\begingroup$ Gerhard, maybe I was a bit sloppy, answer edited. $\endgroup$ Aug 21, 2012 at 19:20
-
$\begingroup$ 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 $\endgroup$ Aug 21, 2012 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.)
Familiarize yourself with the notion of Euler characteristic
Convince yourself that the Euler characteristic of your triangulation of a rectangle is 1.
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.