1
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ Finite or infinite? $\endgroup$ Aug 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$ Aug 21, 2012 at 14:59
  • 1
    $\begingroup$ I can only see how to do $6$ regions. An octahedron is a closed manifold. $\endgroup$
    – Will Sawin
    Aug 21, 2012 at 17:46

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
4
  • $\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
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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