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

<p>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.</p>

<p>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. </p>

<p>EDIT:</p>

<p>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: </p>

<p>SECOND ARGUMENT:</p>

<p>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.$$</p>

<p><img src="https://i.sstatic.net/tlrrc.jpg" alt="geometry picture"></p>

<p>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)\,).$$</p>

<p>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.</p>

<p>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 &lt; 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. </p>

CC BY-SA 3.0
2011-12-21T20:50:33.400Z
I didn't expect this question to be that tricky :). eagerly awaiting the pictures.
Suresh Venkat
CC BY-SA 3.0
2011-12-21T03:33:22.447Z
2011-12-21T21:27:03.917Z
2011-12-21T21:27:03.917Z
Peter Shor 
<p>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). </p>

<p>Inspired by but unrelated to <a href="https://math.stackexchange.com/questions/92916/vertices-arrangement-on-the-unit-sphere">this question</a> on Math.SE.</p>

CC BY-SA 3.0
2011-12-20T22:22:07.687Z
How does one define Delaunay triangulation on the sphere?
someone
CC BY-SA 3.0
2011-12-20T22:26:58.690Z
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.
Josephine Moeller
CC BY-SA 3.0
2011-12-20T22:47:41.340Z
One way is 'geodesically', via the empty ball property. Namely, three points on the sphere form a Delaunay triangle if their circumscribing sphere is empty.
Suresh Venkat
CC BY-SA 3.0
2011-12-20T22:48:55.550Z
@JohnMoeller true. But even in the negatively curved case, while triangles would end up getting pinched, it might still be that the Delaunay triangulation (with facets being empty geodesic balls) has "less pinched" triangles ?
Suresh Venkat
CC BY-SA 3.0
2011-12-20T22:58:15.350Z
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?
someone
CC BY-SA 3.0
2011-12-20T23:01:14.673Z
@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.
Josephine Moeller
CC BY-SA 3.0
2011-12-20T23:13:00.207Z
@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.
Josephine Moeller
CC BY-SA 3.0
2011-12-20T23:26:33.803Z
@someone I too did not realize that the stereographic map is conformal, and it sounds like that should do it. Maybe you should post an answer ?
Suresh Venkat
CC BY-SA 3.0
2011-12-20T23:52:25.323Z
On the plane, the outer face of a Delaunay triangulation doesn't have to be a triangle.  But, if we think about a Delaunay triangulation on the sphere, all faces are triangles if points are in general position, unless I have a terrible mistake.  So, I'm not sure if the correspondence is so direct...
Yoshio Okamoto
CC BY-SA 3.0
2011-12-20T23:55:32.680Z
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.
Peter Shor 
CC BY-SA 3.0
2011-12-21T00:03:11.373Z
Update on my comment: Probably it's easier to imagine the situation in Voronoi diagrams.  On the plane, we have some unbounded edges, and the projecting them on the sphere gives us arcs having the north pole as endpoints.  So, the north pole needs to be a degenerate vertex (of the Voronoi diagram), but this doesn't have to be the case if you're given a point set on the sphere.
Yoshio Okamoto
CC BY-SA 3.0
2011-12-21T00:06:40.633Z
@PeterShor Ah, yes, of course. Too big of a hitch.
Josephine Moeller
<cg.comp-geom><delaunay-triangulation>
Do Delaunay triangulations on the sphere maximize the minimum angle?
Suresh Venkat
# Do Delaunay triangulations on the sphere maximize the minimum angle?

(Asked by: username_0 on 2011-12-20)

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](https://math.stackexchange.com/questions/92916/vertices-arrangement-on-the-unit-sphere) on Math.SE.

**Tags:** cg.comp-geom, delaunay-triangulation
> **Comments:**
> **username_1**: How does one define Delaunay triangulation on the sphere?  
> **username_2**: 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.  
> **username_0**: One way is 'geodesically', via the empty ball property. Namely, three points on the sphere form a Delaunay triangle if their circumscribing sphere is empty.  
> **username_0**: @JohnMoeller true. But even in the negatively curved case, while triangles would end up getting pinched, it might still be that the Delaunay triangulation (with facets being empty geodesic balls) has "less pinched" triangles ?  
> **username_1**: 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?  
> **username_2**: @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.  
> **username_2**: @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.  
> **username_0**: @someone I too did not realize that the stereographic map is conformal, and it sounds like that should do it. Maybe you should post an answer ?  
> **username_3**: On the plane, the outer face of a Delaunay triangulation doesn't have to be a triangle.  But, if we think about a Delaunay triangulation on the sphere, all faces are triangles if points are in general position, unless I have a terrible mistake.  So, I'm not sure if the correspondence is so direct...  
> **username_4**: 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.  
> **username_3**: Update on my comment: Probably it's easier to imagine the situation in Voronoi diagrams.  On the plane, we have some unbounded edges, and the projecting them on the sphere gives us arcs having the north pole as endpoints.  So, the north pole needs to be a degenerate vertex (of the Voronoi diagram), but this doesn't have to be the case if you're given a point set on the sphere.  
> **username_2**: @PeterShor Ah, yes, of course. Too big of a hitch.  

---

## 1 answers

### Answer by username_4 on 2011-12-21. Score: 10 | Accepted answer

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](https://i.sstatic.net/tlrrc.jpg)

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.

> **Comments:**
> **username_0**: I didn't expect this question to be that tricky :). eagerly awaiting the pictures.  

---

