Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

3 Answers 3

up vote 1 down vote accepted
+50

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.

share|improve this answer
1  
Great response. What you call "sub-hull" is also known as the second convex layer and the problem of finding all convex layers is sometimes called the onion peeling problem. This other question of mine about convex layers might interest you. –  rrufai May 27 '13 at 13:36
    
Actually, your other question points out a subtle flaw in the argument. According to the results of that question, the convex hull from a uniform distribution on a $k$-gon is $O(k\log n)$ and on a smooth convex shape is $O(n^{1/3})$. Thus for the circle the argument still goes through (with $O(n^{1/3})$ in the hull and sub-hull), but in a $k$-gon there are $O(\log n)$ in the hull and $O(\log^2 n)$ in the sub-hull, so I would actually amend the claim to say that hull vertices have $O(\log n)$ average degree in a $k$-gon (because the second hull is "rounder" than the first). –  Mario Carneiro May 27 '13 at 19:23

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.

share|improve this answer
    
I've added clarification to the question. $P$ is random drawn from a uniform distribution of points within the unit square, say. –  rrufai May 21 '12 at 21:12
    
For the case you describe, the hull vertices would have average degrees of $\frac{n + 3}{3} = O(n)$. But this has to be a specially crafted point set. When $P$ is drawn uniformly and independently from a unit square or a unit disk, what can we say about the expected degree of a hull vertex in such a case? –  rrufai Sep 5 '12 at 16:24

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.

share|improve this answer
    
Let $P=\{p_1, p_2, ..., p_n\}$ be an arbitrary point set from $\mathbb{R}^2$ in general position. Let $Q = \{q_1, q_2, ..., q_h\}$ be the subset of $P$ that form the convex hull vertices of $P$. In the delaunay triangulation of $P$, the average degree of the hull vertices $Q$ is defined by $\frac{\sum_i^h deg(q_i) }{h}$. Clearly, the sum $\sum_i^h deg(q_i)$ could not be $O(1)$, but the question will be equivalent to saying that the sum is logarithmic. –  rrufai Jul 15 '12 at 22:53
    
Okay, I see. Then this might be a tricky question, since triangles on the boundary of the convex hull tend to be skinny. This might be an indication that the $O(1)$ bound for the average degree does not hold. Maybe people in the mesh-generating community know more about this. –  A.Schulz Jul 18 '12 at 12:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.