Random observation that I don't recall seeing before: the edges from the sequence of convex hulls of a shelling of a point set forms a pointed pseudotriangulation: that is, it's a planar graph in which each interior face has three convex vertices and each vertex has one reflex angle.

But not every pointed pseudotriangulation can come from a shelling in this way: one can only have pseudotriangles with a single chain of reflex vertices, and there's some sort of acyclicity condition on the direction these chains can point. So the pseudotriangulations below do not come from shellings:

Two pointed pseudotriangulations that do not come from shellings

Since shellings are closely related to antimatroids, and antimatroids are related to certain kinds of greedy algorithms, perhaps this connection can lead to some algorithms for finding optimal pseudotriangulations...


Comments:

None:
2007-02-18T03:49:19Z

Check out this writeup - it might be remotely related. --S

11011110:
2007-02-18T04:49:43Z

I would have found this had you used the word "shelling"...

The degree restriction you use stops your version of this shelling process from forming an antimatroid, though: a point can be admissable, then stop being admissable because the removal of some other points increases its degree.

Also note that your tents are not exactly the same things as pseudotriangles; e.g. the central pseudotriangle in the pentagon in the left side of my figure is not a tent for any subset of the point set.

None:
2007-02-19T06:43:44Z

I said "remotely related" ;). Anyway, you can choose the vertex randomly, and then the result holds in expectation, removing the degree restriction.