Problem statement

Marc van Kreveld asks, given a set of n points, how many combinatorially different Delaunay triangulations can you get if you are allowed to affinely transform the point set? (Or equivalently, if you replace you cirlce by a rotated ellipse?)

It is between Omega(n^2) and O(n^4), but we should be able to tell.

Mark's email

At Dagstuhl we talked about anisotropic Delaunay triangulations. We had a quadratic upper bound on the number of them, proved via a lifting map and then the upper bound theorem applied to convex polytopes in 5-space.

Either I still do not understand it fully, or it is not correct. I am attaching the photo of the whyteboard, and a description of what I think the reasoning in Dagstuhl was. Perhaps you can enlighten me. (I do see that the argument gives an n^4 upper bound.)

The idea was to lift the points in the plane to points (or hyperplanes?) in 5-space, so that ellipses become hyperplanes (or points, but that would simply be the dual situation to this). 5 points that define an empty ellipse E are mapped such that the ellipse is a hyperplane through the 5 points in 5-space, and all other points of the set lie above this hyperplane. This gives the connection to convex hulls, and all 4-faces of the lower convex hull of the lifted points correspond to empty ellipses through 5 points in the plane.

Now two of the dimensions in 5-space were called A and T (see picture), which are essentially defined by the transformation that takes any ellipse-shape to a unit disc, which is defined by two parameters. These two parameters give the A and T. Any point in the AT-plane in 5-space corresponds to some transformation. The subspace with fixed A and T is a 3-flat in 5-space, and the intersection of this 3-flat with the convex polytope we get from the lifted points corresponds to some anisotropic Delaunay triangulation (the one for this A and T). The question then becomes how many combinatorially distinct intersections we can have between all 3-flats (two degrees of freedom, A and T) and the convex polytope with n vertices and n^2 faces of higher dimensions.

I don't see why this should be only quadratic. A 3-flat in 5-space generally intersects 2-faces, 3-faces and 4-faces of the boundary of the 5-polytope. When we translate the 3-flat, a combinatorially different intersection is obtained when the 3-flat crosses a 1-face. And there are only n^2 of these. I get that much. And I guess this is where my 5D intuition stops, to see why this implies, even when we translate in 2 directions, we only get n^2. Or was there another argument involved that I am missing now?

As I see it (or used to see it), in the AT-plane there are critical curves defined by quadruples of points that are in convex position and define an empty ellipse of some shape. The lifting map shows that there are only n^2 of such quadruples, which correspond to the 3-faces of the polytope. Two critical curves my intersect, and generally the curves are defined by disjoint quadruples. This means that eight points define a vertex in the AT-plane. How does this correspond to the situation in 5-space?

The other open question that remains is: for any point q (not in P) in the plane, in how many anisotropic triangles does it lie? Quadratic or linear?

My bumbling

I am hoping that if things go wrong, they go wrong for a stretched moment curve, so I did some MATLAB hacking on that case. I realized when I was done that I'm looking at hyperbolas instead of ellipses, so significant parts of what I say in the rest of this message is bogus. I send this faulty analysis anyway just to continue the conversation...

---

I'd like to construct the space of ellipses for points (i^3, i), for i=1:n. Lift these to tuples [x^2 xy y^2 x y 1] = [i^6 i^4 i^2 i^3 i 1], which we could think of a points on a stretched moment curve, but I would rather think of them in the dual as hyperplanes in a homogeneous space, because then we get a homog space of ellipses (1 A B C D E) where a point is on an ellipse iff (1 A B C D E)*[x^2 xy y^2 x y 1] = 0 and outside if the dot product is positive.

I also need to restrict myself to the region with B-(A^2)/4 > 0 to have ellipses rather than hyperbolas. So I have the intersection of this region with a polytope that defines all possible empty ellipses (of all rotations, and aspect ratios, scales, and translations). We know that if we fix A and B we have chosen a rotation and aspect ratio for our ellipse, and computing empty circles will determine the C, D, E parameters. We want to see when different choices of AB give combinatorially different anisotropic DTs.

Following your suggestion, let's look for critical curves in the AB plane. These are the points where an ellipse with parameters AB can go through 4 sites, so that we would have a diagonal flip in the corresponding DT of transformed points. Note that these are projections into the AB plane of the intersection of 4 hyperplanes, so they are lines or line segments. We can move along a line until we hit a fifth point with the ellipse or the boundary of the ellipse region. Since the discriminant B-(A^2)/4 is non-linear but convex, I thought I'd just overcount by projecting all the 5-point ellipses as vertices of the polytope and project them to vertices in the AB plane.

We know that the polytope has only O(n^2) vertices; are there other vertices of the projection that arise from intersections of segments in the AB plane? The attached plot for the points (i^3 i) first made me think that the answer was "no", but it is clearly not the right plot because it doesn't draw any lines in the range where they correspond to ellipses -- they are all hyperbolas. (Maybe I'm drawing the wrong segment of these great circles?)

This plot was constructed as follows: Determine the 5-tuples of points that define empty conics, and determine the AB parameters of the vertices to plot their projections. Not surprisingly, the 5-tuples are those with i = (1 j j+1 k k+1), giving Theta(n^2) vertices of the polytope; For what it is worth, Maple tells me that the parameters for this vertex are A = -(3*j^2+(7+4*k)*j+3*k^2+7*k+6) B = -((4+4*k)*j^3+(13+23*k+7*k^2)*j^2+(23*k^2+35*k+4*k^3+13)*j+13*k+3+4*k^3+13*k^2) I had a sign error, so initially I didn't realize that this defined a hyperbola, not an ellipse. I the joined each pair of 5-tuples that intersect in a 4-tuple by an edge to get the attached plot... what's wrong with it? Marc, what did you do to get critical curves, and can you make them linear if you have the right parameterization of the AB/AT space?

-- JackSnoeyink - 02 Apr 2005