9
$\begingroup$

Delaunay triangulations in the plane maximize the minimum angle in a triangle. Does the same hold true for the Delaunay triangulation of points on the sphere ? (here the "angle" is the local angle in a neighborhood around the vertex at the apex).

Inspired by but unrelated to this question on Math.SE.

$\endgroup$
  • 1
    $\begingroup$ Certainly the property would hold for a set localized to a small, flattish region of the sphere, since it's a manifold. The real question would be whether the property is sacrificed as the points spread across the sphere. My guess would be that in order to have a Delaunay triangulation in the first place, you would need fat triangles even more than in the Euclidean case, so the property would hold. $\endgroup$ – Josephine Moeller Dec 20 '11 at 22:26
  • 4
    $\begingroup$ Doesn't this follow then from the fact that stereographic projection from a generic point on the sphere maps circles to circles and preserves the angles between intersecting curves (~edges) because of conformality? Or am I missing something? $\endgroup$ – someone Dec 20 '11 at 22:58
  • 1
    $\begingroup$ @someone Yep, that should do it. At least most of it. There may be a hitch or two, but that would be the central idea. I was wondering about that. I didn't realize that the stereographic mapping was conformal. $\endgroup$ – Josephine Moeller Dec 20 '11 at 23:01
  • 1
    $\begingroup$ @SureshVenkat Now that you mention hyperbolic space, perhaps I have my intuition backward. In hyperbolic space you have to account for the fact that there are "illegal" circumcircles (i.e. hypercycles and horocycles). While in spherical space you don't; you can always find circles that pass through three points. $\endgroup$ – Josephine Moeller Dec 20 '11 at 23:13
  • 7
    $\begingroup$ I don't think this works. You want to make sure the projection takes great circles to lines (since you're measuring the angles between edges of the triangles, which are great circles/straight). I don't think you can't do this with a stereographic projection. You can only do this with a projection from the point at the center of the sphere, which takes some circles to ellipses. $\endgroup$ – Peter Shor Dec 20 '11 at 23:55
10
$\begingroup$

FIRST ARGUMENT: This was my first answer. Note that this argument is wrong. See my second argument below.

I don't think it's true. The reason that it works in the plane is that in a circle, the inscribed angle subtended by a chord is one half the corresponding central angle. Thus, if we have a triangle with a small angle, any points that would make a larger angle with the opposite edge are inside the empty Delaunay circle, and so aren't one of the points in the configuration we are finding a triangulation of.

Now, suppose you have a Delaunay triangulation on the sphere. Place a point at the center of the sphere, and project all the pionts onto a plane. The edges of the triangles (great circles on the sphere) are all taken to line segments. But the circles giving the empty ball property are taken to ellipses, and so if there's a point outside the projected ellipse but inside the circumcircle of the triangle, this point would make a larger angle with the edge.

EDIT:

Wait a minute. This answer is completely wrong, because the central projection does not preserve angles. I still think the conjecture is wrong, because I have a much more complicated argument that the theorem about inscribed angles does not hold on the sphere. Here's the argument:

SECOND ARGUMENT:

The reason this holds in the plane is that the inscribed angle subtended by a chord is one half the corresponding central angle. That holds because, in the diagram below, we have $$ CYX_2 = \frac{1}{2} (\pi - X_2 C Y)$$ and $$C Y X_1 = \frac{1}{2} (\pi - X_1 C Y).$$ Subtracting, we get $$ X_1 Y X_2 = \frac{1}{2} X_1 C X_2.$$

geometry picture

Now, in spherical geometry, we get $$CYX_2 = \frac{1}{2} ( \pi - X_2CY + A(X_2CY) \,) $$ and $$CYX_1 = \frac{1}{2} ( \pi - X_1CY + A(X_1CY) \,), $$ where $A(XYZ)$ means the area of triangle XYZ. Subtracting, we get $$ X_1 Y X_2 = \frac{1}{2} (X_1 C X_2 + A(X_2CY) - A(X_1CY)\,).$$

For the locus of points $Y$ making a constant angle $X_1YX_2$ to be a circle, we thus need that the difference of areas $A(X_2CY) - A(X_1CY)$ depends only on the arclength $X_1X_2$. However, this is incompatible with the observation that $A(XCY)$ is $0$ for $X$ diametrically opposite $Y$ and for $X=Y$, but grows to some maximum size in between.

Thus, the locus of points $Y$ with constant angle $X_1YX_2$ is not a circle. This means that for some triangle $X_1YX_2$ we can find a point $Y'$ outside the circumcircle of $X_1YX_2$ so the angle $X_1YX_2 < X_1 Y' X_2$. We can then use this to build a counterexample to the conjecture that Delaunay triangulations on the sphere maximize the minimum angle.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ I didn't expect this question to be that tricky :). eagerly awaiting the pictures. $\endgroup$ – Suresh Venkat Dec 21 '11 at 20:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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