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?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
(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.
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!