We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Order-randomized Laplacian mesh smoothing.

Yang, Ying and Rushmeier, Holly and Ivrissimtzis, Ioannis (2017) 'Order-randomized Laplacian mesh smoothing.', in Mathematical methods for curves and surfaces : 9th International Conference, MMCS 2016, Tønsberg, Norway, June 23 - June 28, 2016. Revised selected papers. Cham: Springer, pp. 312-323. Lecture notes in computer science. (10521).


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.

Item Type:Book chapter
Full text:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Publisher statement:The final publication is available at Springer via
Date accepted:07 March 2017
Date deposited:16 August 2017
Date of first online publication:18 October 2017
Date first made open access:18 October 2018

Save or Share this output

Look up in GoogleScholar