<p>I'm looking for an upper bound for the number of triangles in a constrained planar delaunay triangulation. I know for d=2 delaunay triangulation, there are at most n+1 triangles where n is the number of vertices.</p>

<p>Is there any papers or theorems that show that constrained delaunay triangulations have fewer or more triangles than normal delaunay triangulations?</p>

<p><a href="http://www.cs.ucdavis.edu/~amenta/pubs/HiDeeDel.pdf" rel="nofollow">http://www.cs.ucdavis.edu/~amenta/pubs/HiDeeDel.pdf</a></p>

CC BY-SA 3.0
2014-02-22T21:34:56.000Z
For 2d the bound you quote is for simple polygon inputs, right? What definition are you using for constrained Delaunay for higher dimensions?
David Eppstein
CC BY-SA 3.0
2014-02-22T21:40:48.247Z
We're only dealing with 2d for both constrained dt and dt
zaloo
CC BY-SA 3.0
2014-02-23T05:46:26.567Z
But in 2d all triangulations of the same input have the same number of faces. So how could it depend on which type of triangulation you want?
David Eppstein
CC BY-SA 3.0
2014-02-23T07:15:01.923Z
Oh I didn't know that all triangulations for the same input in 2d have the same number of faces. Us there some theorem that states this?
zaloo
CC BY-SA 3.0
2014-02-23T13:02:17.007Z
Euler's formula: V–E+F=2 for any connected planar map with V vertices, E edges, and F faces.
Jeffε
<graph-theory><graph-algorithms><upper-bounds><delaunay-triangulation>
Maximum number of triangles in a constrained delaunay triangulation
zaloo
# Maximum number of triangles in a constrained delaunay triangulation

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

I'm looking for an upper bound for the number of triangles in a constrained planar delaunay triangulation. I know for d=2 delaunay triangulation, there are at most n+1 triangles where n is the number of vertices.

Is there any papers or theorems that show that constrained delaunay triangulations have fewer or more triangles than normal delaunay triangulations?

<http://www.cs.ucdavis.edu/~amenta/pubs/HiDeeDel.pdf>

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

> **Comments:**
> **username_1**: For 2d the bound you quote is for simple polygon inputs, right? What definition are you using for constrained Delaunay for higher dimensions?  
> **username_0**: We're only dealing with 2d for both constrained dt and dt  
> **username_1**: But in 2d all triangulations of the same input have the same number of faces. So how could it depend on which type of triangulation you want?  
> **username_0**: Oh I didn't know that all triangulations for the same input in 2d have the same number of faces. Us there some theorem that states this?  
> **username_2**: Euler's formula: V–E+F=2 for any connected planar map with V vertices, E edges, and F faces.  

---

## 0 answers

