## 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 language | English (US) |
---|---|

Pages (from-to) | 295-300 |

Number of pages | 6 |

Journal | Computer Aided Geometric Design |

Volume | 27 |

Issue number | 4 |

DOIs | |

State | Published - May 2010 |

Externally published | Yes |

## 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