Skip to main content
MathOverflow

Return to Answer

spelling
Source Link
Michael Hardy
Michael Hardy
  • 1
  • 12
  • 85
  • 126

This paper by Bobenko and Izmestiev "Alexandrov's Theorem, Weighted Delaunay Triangulations, and Mixed Volumes" is based upon a generalization of this observation.

One reason that this convex-hull characterization may seem obscure is that it really only applies to points on the sphere. The paragraph in the OP that begins "There is no reason ..." is misleading because it implies that the planar Delaunay triangulation can be characterized in this way. The lower envolopeenvelope of the convex hull of the traditional lifting (to a paraboloid) gives exactly the combinatorics of the planar DT. However, going to a sphere, by stereographic projection, say, is only going to work if the radius of the sphere is "big enough". For a fixed number of points n, there will be no upper bound on the radius that is big enough for all point sets of size n.

The Delaunay triangulation is brittle, and unless unusual demands on the vertex configurations are made, the combinatorial structure can change with an arbitrarily small perturbation of the metric. I.e., the point set can be arbitrarily close to being degenerate.

This paper by Bobenko and Izmestiev "Alexandrov's Theorem, Weighted Delaunay Triangulations, and Mixed Volumes" is based upon a generalization of this observation.

One reason that this convex-hull characterization may seem obscure is that it really only applies to points on the sphere. The paragraph in the OP that begins "There is no reason ..." is misleading because it implies that the planar Delaunay triangulation can be characterized in this way. The lower envolope of the convex hull of the traditional lifting (to a paraboloid) gives exactly the combinatorics of the planar DT. However, going to a sphere, by stereographic projection, say, is only going to work if the radius of the sphere is "big enough". For a fixed number of points n, there will be no upper bound on the radius that is big enough for all point sets of size n.

The Delaunay triangulation is brittle, and unless unusual demands on the vertex configurations are made, the combinatorial structure can change with an arbitrarily small perturbation of the metric. I.e., the point set can be arbitrarily close to being degenerate.

This paper by Bobenko and Izmestiev "Alexandrov's Theorem, Weighted Delaunay Triangulations, and Mixed Volumes" is based upon a generalization of this observation.

One reason that this convex-hull characterization may seem obscure is that it really only applies to points on the sphere. The paragraph in the OP that begins "There is no reason ..." is misleading because it implies that the planar Delaunay triangulation can be characterized in this way. The lower envelope of the convex hull of the traditional lifting (to a paraboloid) gives exactly the combinatorics of the planar DT. However, going to a sphere, by stereographic projection, say, is only going to work if the radius of the sphere is "big enough". For a fixed number of points n, there will be no upper bound on the radius that is big enough for all point sets of size n.

The Delaunay triangulation is brittle, and unless unusual demands on the vertex configurations are made, the combinatorial structure can change with an arbitrarily small perturbation of the metric. I.e., the point set can be arbitrarily close to being degenerate.

Source Link
Ramsay
Ramsay
  • 351
  • 3
  • 4

This paper by Bobenko and Izmestiev "Alexandrov's Theorem, Weighted Delaunay Triangulations, and Mixed Volumes" is based upon a generalization of this observation.

One reason that this convex-hull characterization may seem obscure is that it really only applies to points on the sphere. The paragraph in the OP that begins "There is no reason ..." is misleading because it implies that the planar Delaunay triangulation can be characterized in this way. The lower envolope of the convex hull of the traditional lifting (to a paraboloid) gives exactly the combinatorics of the planar DT. However, going to a sphere, by stereographic projection, say, is only going to work if the radius of the sphere is "big enough". For a fixed number of points n, there will be no upper bound on the radius that is big enough for all point sets of size n.

The Delaunay triangulation is brittle, and unless unusual demands on the vertex configurations are made, the combinatorial structure can change with an arbitrarily small perturbation of the metric. I.e., the point set can be arbitrarily close to being degenerate.