# Properties about verticies in Delaunay Triangulations

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?

-
Sariel's book sarielhp.org/book ? I did an REU project on them a decade ago if you want some examples outside of computational geometry orion.math.iastate.edu/reu/2001/voronoi_paper/voronoi.pdf –  Chad Brewbaker Feb 10 at 22:12
In the plane, in 3-space, or in higher dimensions? –  JɛﬀE Feb 11 at 1:56
The algorithm I am building is only over 2-space –  zaloo Feb 11 at 2:03

## 2 Answers

(In 2-space,) a Delaunay triangulation is a planar graph. All planar graphs have average degree at most 6. So, many (all?) operations that depend on vertex degree of a Delaunay triangulation will run in $O(1)$ expected time.

-
That's amazing, exactly what I needed. –  zaloo Feb 11 at 2:05

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!

-