# 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 Commented Feb 10, 2014 at 22:12
• In the plane, in 3-space, or in higher dimensions? Commented Feb 11, 2014 at 1:56
• The algorithm I am building is only over 2-space Commented Feb 11, 2014 at 2:03

(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.
$\Theta (\log n / \log \log n)$