%0 Journal Article %1 chen10 %A Chen, Renjie %A Xu, Yin %A Gotsman, Craig %A Liu, Ligang %D 2010 %J Computer Aided Geometric Design %K delaunay dirichlet.energy spectral.graph.theory triangulation %N 4 %P 295--300 %R 10.1016/j.cagd.2010.02.002 %T A Spectral Characterization of the Delaunay Triangulation %V 27 %X 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.

@article{chen10, 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.}, added-at = {2012-12-28T19:10:59.000+0100}, author = {Chen, Renjie and Xu, Yin and Gotsman, Craig and Liu, Ligang}, biburl = {https://www.bibsonomy.org/bibtex/2564a778814dfbf93c23f7a458f3cbbe3/ytyoun}, doi = {10.1016/j.cagd.2010.02.002}, interhash = {7fbfdc4f6bcfc8e6b4f3e84a2749c044}, intrahash = {564a778814dfbf93c23f7a458f3cbbe3}, issn = {0167-8396}, journal = {Computer Aided Geometric Design}, keywords = {delaunay dirichlet.energy spectral.graph.theory triangulation}, number = 4, pages = {295--300}, timestamp = {2016-11-16T07:50:01.000+0100}, title = {A Spectral Characterization of the {Delaunay} Triangulation}, volume = 27, year = 2010 }