A spectral characterization of the Delaunay triangulation

Renjie Chen, Yin Xu, Craig Gotsman, Ligang Liu

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)295-300
Number of pages6
JournalComputer Aided Geometric Design
Volume27
Issue number4
DOIs
StatePublished - May 2010
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Modeling and Simulation
  • Automotive Engineering
  • Aerospace Engineering
  • Computer Graphics and Computer-Aided Design

Keywords

  • Delaunay triangulation
  • Dirichlet energy
  • Laplacian
  • Spectrum

Fingerprint Dive into the research topics of 'A spectral characterization of the Delaunay triangulation'. Together they form a unique fingerprint.

Cite this