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 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

2 Answers 2

up vote 2 down vote accepted

Only if you have few enough triangles. You can split the domain with a diagonal into two triangles and each vertex has at most 3. It helps to think about the total angle around the vertices. You have four vertices at the corners that contribute a total of $2\pi$ in angle. Each vertex on the edge of the rectangle contributes $\pi$ and each vertex inside the rectangle contributes $2\pi$. If you have no added points, you need two triangles to supply the $2\pi$. Each point on the edge adds $\pi$ to the total angle, so adds one triangle. Each point in the interior adds $2\pi$ to the total angle, so you need two more triangles. You can only have twice as many edges as vertices, so letting $V_a$ be the number of vertices on the edge (including the corners), $V_b$ the number of vertices inside, $E$ the number of edges, and $F$ the number of faces (one more than the number of triangles to count the exterior region) we have $V_a+V_b-E+F=2, F-1=2+(V_a-4)+2V_b, E \le 2(V_a+V_b)$, so $2V_a+3V_b-E=3$. Clearly $V_b$ has to stay small. It works with $1,2$, but not with $3$

The above assumes that it is not acceptable to have a vertex in the middle of one side of a triangle. If that restriction is removed, you can have more points in the interior, as shown below. You can also cut up the rectangle in other ways.

enter image description here

share|improve this answer

I don't know what requirements you have for your "grid"; but here is a way to triangulate an arbitrary convex quadrilateral with vertices $A_m^0$ ($m \in \mathbb Z_4$) with any number of triangles such that every vertex of the resulting figure is the meet of either 3 or 4 edges. Let $O$ be an interior point of the quadrilateral. At stage $n$ ($n \in \mathbb N$), for each $m$ in $\mathbb Z_4$, draw an edge from $A_m^n$ to an interior point $A_{m'}^{n+1}$ of the line segment $OA_{m'}^n$ , where $$m'=\begin{cases} m+1 & \text{ if } n \text{ is even,} \\ m-1& \text{ if } n \text{ is odd.} \end{cases}$$ The process can be interrupted when you have the required number of triangles. This method allows considerable choice in the shape of the triangles, although some will perforce be very small or very thin if the number is large.

share|improve this answer

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.