Publication details for Dr Ioannis IvrissimtzisYang, Ying, Rushmeier, Holly & Ivrissimtzis, Ioannis (2017), Order-randomized Laplacian mesh smoothing, in Floater, Michael S., Lyche, Tom, Mazure, Marie-Laurence, Mørken, Knut & Schumaker, Larry L. eds, Lecture Notes in Computer Science 10521: 9th International Conference on Mathematical Methods for Curves and Surfaces. Tønsberg, Norway, Springer, Cham, 312-323.
- Publication type: Conference Paper
- ISSN/ISBN: 9783319678849, 9783319678856, 0302-9743, 1611-3349
- DOI: 10.1007/978-3-319-67885-6_17
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
Author(s) from Durham
In this paper we compare three variants of the graph Laplacian smoothing. The first is the standard synchronous implementation, corresponding to multiplication by the graph Laplacian matrix. The second is a voter process inspired asynchronous implementation, assuming that every vertex is equipped with an independent exponential clock. The third is in-between the first two, with the vertices updated according to a random permutation of them. We review some well-known results on spectral graph theory and on voter processes, and we show that while the convergence of the synchronous Laplacian is graph dependent and, generally, does not converge on bipartite graphs, the asynchronous converges with high probability on all graphs. The differences in the properties of these three approaches are illustrated with examples including both regular grids and irregular meshes.