Analyzing the squared distance-to-measure gradient flow system with k-order Voronoi diagrams

68. Patrick O'Neil, Thomas Wanner:
    Analyzing the squared distance-to-measure gradient flow system with k-order Voronoi diagrams
    Discrete & Computational Geometry 61(1), pp. 91-119, 2019.

Abstract

Point cloud data arises naturally from 3-dimensional scanners, LiDAR sensors, and industrial computed tomography (i.e. CT scans) among other sources. Most point clouds obtained through experimental means exhibit some level of noise, inhibiting mesh reconstruction algorithms and topological data analysis techniques. To alleviate the problems caused by noise, smoothing algorithms are often employed as a preprocessing step. Moving least squares is one such technique, however, many of these techniques are designed to work on surfaces in $\mathbb{R}^3$. As interesting point clouds can naturally live in higher dimensions, we seek a method for smoothing higher dimensional point clouds. To this end, we turn to the distance to measure function. In this paper, we provide a theoretical foundation for studying the gradient flow induced by the squared distance to measure function, as introduced by Chazal, Cohen-Steiner, and Merigot. In particular, we frame the gradient flow as a Filippov system and find a method for solving the squared distance to measure gradient flow, induced by the uniform empirical measure, using higher order Voronoi diagrams. In contrast to some existing techniques, this gradient flow provides a smoothing algorithm which computationally scales with dimensionality.

Links

The published version of the paper can be found at https://doi.org/10.1007/s00454-018-0037-6. The associated code can be found at https://github.com/ponl/GradSmooth.

Bibtex

@article{oneil:wanner:19a,
   author = {Patrick O'Neil and Thomas Wanner},
   title = {Analyzing the squared distance-to-measure gradient flow
            system with $k$-order {V}oronoi diagrams},
   journal = {Discrete \& Computational Geometry},
   volume = {61},
   number = {1},
   year = {2019},
   pages = {91--119},
   doi = {10.1007/s00454-018-0037-6}
   }