<p>(In 2-space,) a Delaunay triangulation is a planar graph. <a href="http://en.wikipedia.org/wiki/Planar_graph#Average_degree" rel="nofollow">All planar graphs have average degree at most 6</a>. So, many (all?) operations that depend on vertex degree of a Delaunay triangulation will run in $O(1)$ expected time.</p>

CC BY-SA 3.0
2014-02-11T02:05:42.343Z
That's amazing, exactly what I needed.
zaloo
CC BY-SA 3.0
2014-02-11T00:23:37.320Z
2014-02-11T12:54:45.940Z
2014-02-11T12:54:45.940Z
Daniel Apon
<p>Here's a theta bound on the expected value of the maximum degree of any vertex in a DT:</p>

<p>$\Theta (\log n / \log \log n)$</p>

<p>Here's the paper: <a href="http://www.ics.uci.edu/~eppstein/pubs/BerEppYao-IJCGA-91.pdf" rel="nofollow">http://www.ics.uci.edu/~eppstein/pubs/BerEppYao-IJCGA-91.pdf</a>. If anyone else finds other properties, let me know!</p>

CC BY-SA 3.0
2014-02-10T21:42:42.110Z
2014-02-10T21:59:41.097Z
2014-02-10T21:59:41.097Z
zaloo
<p>I'm working on my thesis dealing with pathfinding over Delaunay triangulations. I have an algorithm that has running time in time proportional to the degree of a vertex. Are there any properties or upper bounds on the degree of vertices in a Delaunay (or Constrained Delaunay) triangulation?</p>

CC BY-SA 3.0
2014-02-10T22:12:18.150Z
Sariel's book http://sarielhp.org/book/ ? I did an REU project on them a decade ago if you want some examples outside of computational geometry http://orion.math.iastate.edu/reu/2001/voronoi_paper/voronoi.pdf
Chad Brewbaker
CC BY-SA 3.0
2014-02-11T01:56:57.060Z
In the plane, in 3-space, or in higher dimensions?
Jeffε
CC BY-SA 3.0
2014-02-11T02:03:54.117Z
The algorithm I am building is only over 2-space
zaloo
<graph-theory><graph-algorithms><delaunay-triangulation>
Properties about verticies in Delaunay Triangulations
zaloo
# Properties about verticies in Delaunay Triangulations

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

I'm working on my thesis dealing with pathfinding over Delaunay triangulations. I have an algorithm that has running time in time proportional to the degree of a vertex. Are there any properties or upper bounds on the degree of vertices in a Delaunay (or Constrained Delaunay) triangulation?

**Tags:** graph-theory, graph-algorithms, delaunay-triangulation
> **Comments:**
> **username_1**: Sariel's book http://sarielhp.org/book/ ? I did an REU project on them a decade ago if you want some examples outside of computational geometry http://orion.math.iastate.edu/reu/2001/voronoi_paper/voronoi.pdf  
> **username_2**: In the plane, in 3-space, or in higher dimensions?  
> **username_0**: The algorithm I am building is only over 2-space  

---

## 2 answers

### Answer by username_3 on 2014-02-11. Score: 4 | Accepted answer

(In 2-space,) a Delaunay triangulation is a planar graph. [All planar graphs have average degree at most 6](http://en.wikipedia.org/wiki/Planar_graph#Average_degree). So, many (all?) operations that depend on vertex degree of a Delaunay triangulation will run in $O(1)$ expected time.

> **Comments:**
> **username_0**: That's amazing, exactly what I needed.  

---

### Answer by username_0 on 2014-02-10. Score: 2

Here's a theta bound on the expected value of the maximum degree of any vertex in a DT:

$\Theta (\log n / \log \log n)$

Here's the paper: <http://www.ics.uci.edu/~eppstein/pubs/BerEppYao-IJCGA-91.pdf>. If anyone else finds other properties, let me know!


---

