<p>I think only those vertices corresponding to triangles sharing an edge with boundary or holes of the polygon will be of degree less than 3. Now the number of triangles in the triangulation is fixed. So you can always get the exact ratio of the number of degree 3 vertices for a polygon.</p>

<p>If the polygon has $k$ vertices and $l$ holes vertices and the number of triangles in the total triangulation is $N$ 
then the upper bound should be $(N-K-l)/N$.</p>

CC BY-SA 3.0
2014-02-22T15:01:39.353Z
Yes but I believe N might be dependent on k and l, so we may be able to say more
zaloo
CC BY-SA 3.0
2014-02-22T19:23:09.413Z
For $p$ points the total number of triangles are $2p-2-k$ triangles where $k$ is the number of points on the convex hull.In your case, it seems from the image that $k=4$. And for each hole you have two triangles. So the expression for total number of triangles becomes i think $N=2*p-6-2*h$. Each hole again has only 4 boundaries so, the ratio now becomes $(2*p-10-6*h)/(2*p-6-2*h)$.
Dibyayan
CC BY-SA 3.0
2014-02-22T13:02:43.200Z
2014-02-22T13:02:43.200Z
Dibyayan
<p>I'm working on a triangle partitioning problem, and I'm trying to find and prove some properties of specific triangulations. The triangulations I'm dealing with are constrained delaunay triangulations in which every constraint is at least an edge (there are no single vertex constraints). Here is an example of such a triangulation:</p>

<p><img src="https://i.sstatic.net/zxMyi.png" alt="enter image description here"></p>

<p>The red lines represent edge constraints and the blue lines represent the unconstrained edges produced to create the triangulation. Notice how all vertices are in some edge constraint and that there will never be a vertex that is not connected to a constrained edge.</p>

<p>Now let us create a graph from this triangulation. Every triangle is a vertex, and edges are defined by $(v_1,v_2)$ where $v_1$ and $v_2$ are triangles that share an unconstrained edge. Notice that every vertex in this graph has degree at most 3.</p>

<p>My problem is that I want to say something about the number of 3 degree vertices in such a graph. I believe that at least half the vertices have less than degree 3 (just from a hunch) but I have no idea how to go about proving such a thing. What I'm asking is, what is the upper bound of the ratio degree 3 vertices to total vertices in a triangulation with these properties.</p>

<p>EDIT: I found this on the delaunay triangulation wikipedia page. Delaunay triangulations have $O(n^{d/2})$ simplicies, so a planar DT would have $O(n)$ triangles where $n$ is the number of vertices. This isn't the same as the set of constrained delaunay triangulations we're working with, but it seems to suggest that there could be a relationship degree-3 triangles and the total number of triangles.</p>

<p><a href="http://www.sciencedirect.com/science/article/pii/092577219500013Y" rel="nofollow noreferrer">http://www.sciencedirect.com/science/article/pii/092577219500013Y</a></p>

CC BY-SA 3.0
2014-07-22T21:38:44.650Z
Are you sure we can always obtain a delaunay triangulation? May be input configuration is in such a way that doesn't allow any possible delaunay triangulation. (I don't know if such an input exists or not but if you have a criteria such that every input configuration admits delaunay triangulation, then is better to mention it in the question).
Saeed
CC BY-SA 3.0
2014-07-25T17:16:53.930Z
We don't need a delaunay triangulation, just a constrained delaunay triangulation (which is not necessarily delaunay). You are totally right that these inputs may not have a possible delaunay triangulation, but they will always have possible constrained delaunay triangulations!
zaloo
CC BY-SA 3.0
2014-07-25T22:28:30.713Z
So I got confused. Are you looking for just triangulation? (according to your constrains, let call it constrained triangulation). If this is the case then I'd suggest to remove word delaunay from question body and title. Because x-delaunay-triangulation has very solid meaning, and it doesn't mean just triangulation (with your x-constrains).
Saeed
<graph-theory><graph-algorithms><delaunay-triangulation>
Number of "3-edge" triangles in a planar triangulation
zaloo
# Number of "3-edge" triangles in a planar triangulation

(Asked by: username_0 on 2014-02-21)

I'm working on a triangle partitioning problem, and I'm trying to find and prove some properties of specific triangulations. The triangulations I'm dealing with are constrained delaunay triangulations in which every constraint is at least an edge (there are no single vertex constraints). Here is an example of such a triangulation:

![enter image description here](https://i.sstatic.net/zxMyi.png)

The red lines represent edge constraints and the blue lines represent the unconstrained edges produced to create the triangulation. Notice how all vertices are in some edge constraint and that there will never be a vertex that is not connected to a constrained edge.

Now let us create a graph from this triangulation. Every triangle is a vertex, and edges are defined by $(v\_1,v\_2)$ where $v\_1$ and $v\_2$ are triangles that share an unconstrained edge. Notice that every vertex in this graph has degree at most 3.

My problem is that I want to say something about the number of 3 degree vertices in such a graph. I believe that at least half the vertices have less than degree 3 (just from a hunch) but I have no idea how to go about proving such a thing. What I'm asking is, what is the upper bound of the ratio degree 3 vertices to total vertices in a triangulation with these properties.

EDIT: I found this on the delaunay triangulation wikipedia page. Delaunay triangulations have $O(n^{d/2})$ simplicies, so a planar DT would have $O(n)$ triangles where $n$ is the number of vertices. This isn't the same as the set of constrained delaunay triangulations we're working with, but it seems to suggest that there could be a relationship degree-3 triangles and the total number of triangles.

<http://www.sciencedirect.com/science/article/pii/092577219500013Y>

**Tags:** graph-theory, graph-algorithms, delaunay-triangulation

> **Comments:**
> **username_1**: Are you sure we can always obtain a delaunay triangulation? May be input configuration is in such a way that doesn't allow any possible delaunay triangulation. (I don't know if such an input exists or not but if you have a criteria such that every input configuration admits delaunay triangulation, then is better to mention it in the question).  
> **username_0**: We don't need a delaunay triangulation, just a constrained delaunay triangulation (which is not necessarily delaunay). You are totally right that these inputs may not have a possible delaunay triangulation, but they will always have possible constrained delaunay triangulations!  
> **username_1**: So I got confused. Are you looking for just triangulation? (according to your constrains, let call it constrained triangulation). If this is the case then I'd suggest to remove word delaunay from question body and title. Because x-delaunay-triangulation has very solid meaning, and it doesn't mean just triangulation (with your x-constrains).  

---

## 1 answers

### Answer by username_2 on 2014-02-22. Score: 1

I think only those vertices corresponding to triangles sharing an edge with boundary or holes of the polygon will be of degree less than 3. Now the number of triangles in the triangulation is fixed. So you can always get the exact ratio of the number of degree 3 vertices for a polygon.

If the polygon has $k$ vertices and $l$ holes vertices and the number of triangles in the total triangulation is $N$
then the upper bound should be $(N-K-l)/N$.

> **Comments:**
> **username_0**: Yes but I believe N might be dependent on k and l, so we may be able to say more  
> **username_2**: For $p$ points the total number of triangles are $2p-2-k$ triangles where $k$ is the number of points on the convex hull.In your case, it seems from the image that $k=4$. And for each hole you have two triangles. So the expression for total number of triangles becomes i think $N=2*p-6-2*h$. Each hole again has only 4 boundaries so, the ratio now becomes $(2*p-10-6*h)/(2*p-6-2*h)$.  

---

