Average degree of convex hull vertices in a Delaunay triangulation Let $P \subset \mathbb{R}^2$. The boundary of $DT(P)$, the Delaunay triangulation of the point set $P$, is  $conv(P)$. It is also known that the average degree of the vertices of $DT(P)$ is $\lt 6$. My question is there any known bound on the expected degree of the hull vertices of $DT(P)$? Is there an intuitive argument at least for this bound to also be $O(1)$?
Edit: Consider the two cases:
Case 1: $P$ is drawn uniformly and independently from the unit square.
Case 2: $P$ is drawn uniformly and independently from the unit disk.
Are there known results for point sets with other distributions? Any valuable reference on this questions?
 A: I don't know if I understood you correctly, I also don't know the probability space (i.e. if $P$ is random in $\mathbb{R}^2$, and if yes, then what is the distribution). However, if $P$ is fixed, then the answer is probably no, i.e. the average degree (for any Delaunay triangulation) may be arbitrarily high. Just take $P$ to be a regular $(n-3)$-gon and add 3 more points such that the rest will be strictly contained in the resulting triangle, that means the convex hull of $P$ will be those three points. In any triangulation each point of the circle will have to connect to some point of the hull, and there are only $O(1)$ of them, so the average degree must be high.
A: It is not quite clear for me if you mean the average degree of the convex hull vertices or the sum of the degrees of the convex hull vertices. In the latter case the fact that the expected number of vertices on the convex hull is $O(\log n)$ would make a $O(1)$ bound surprising.
A: I have an intuitive argument for why the average degree of the hull vertices should still be $O(1)$ when the point set is drawn uniformly from a convex shape (like a unit square or unit disk).
The environment of a hull vertex is much "the same" as the internal vertices with respect to nearby other vertices, except that there are no vertices on one side of it. Stated another way, if I take some convex shape and generate points uniformly inside it, then slice it down the middle and throw away all the points on one side, the resulting point set may as well have come from a uniform distribution on the new shape, but some points that were previously internal vertices are now hull vertices, and the point distribution on one side is the same as it was before, when they were internal vertices. This means that hull vertices don't have to worry about neighbor points being any closer or farther away than normal, just that the distribution is only on one side.
Okay, so the points "look" the same at a hull vertex, except there are only half as many and they are all on one side. But what about the edges? Surely as a hull vertex, more edges will come to them than if they were deep in the middle. Well, we can estimate the edges at the hull to good approximation by considering the "sub-hull", which I define as $\operatorname{conv}(P-\operatorname{conv}(P))$, i.e. the points in the convex hull of the points that remain after you remove the true convex hull points. These are the "faraway" points that will form edges with the hull points simply because there are no closer points on the other side of the hull to connect to.
There are $O(\log n)$ hull points and $O(n)$ points, so $|P-\operatorname{conv}(P)|$ is also $O(n)$ and the sub-hull is also $O(\log n)$. Thus (I'm ignoring a lot of variables because I'm only after a big-$O$ estimate) there will be on average $O(1)$ connections from adjacent hull points and sub-hull points, and $O(1)$ from nearby points (this is the factor that internal vertices have, perhaps divided by $2$), for a total of $O(1)$ edges at a typical hull point.
Note: This is not even close to a mathematical proof, but it should give at least strong evidence to believe that hull vertices have $O(1)$ average degree.
