A spectral characterization of the Delaunay triangulation

作者：Chen, Renjie; Xu, Yin; Gotsman, Craig^*; Liu, Ligang

来源：Computer Aided Geometric Design, 2010, 27(4): 295-300.

DOI：10.1016/j.cagd.2010.02.002

• Delaunay triangulation
• Laplacian
• Spectrum
• Dirichlet energy

The Delaunay triangulation of a planar point set is a fundamental construct in computational geometry. A simple algorithm to generate it is based on flips of diagonal edges in convex quads. We characterize the effect of a single edge flip in a triangulation on the geometric Laplacian of the triangulation, which leads to a simpler and shorter proof of a theorem of Rippa that the Dirichlet energy of any piecewise-linear scalar function on a triangulation obtains its minimum on the Delaunay triangulation. Using Rippa's theorem, we provide a spectral characterization of the Delaunay triangulation, namely that the spectrum of the geometric Laplacian is minimized on this triangulation. This spectral theorem then leads to a simpler proof of a theorem of Musin that the harmonic index also obtains its minimum on the Delaunay triangulation.

• 出版日期2010-5
• 单位浙江大学