In recent years new application areas have emerged in which one aims to capture the geometry of objects by
means of three-dimensional point clouds, e.g., via LiDAR, stereo vision, or depth-by-motion techniques. Often
the obtained data consist of a dense sampling of the object's surface, containing many redundant 3D points.
These unnecessary data samples lead to high computational effort in subsequent processing steps. Thus, point
cloud sparsification or compression is often applied as a preprocessing step. The two standard methods to
compress dense 3D point clouds are random subsampling and approximation schemes based on hierarchical tree
structures, e.g., octree representations. However, both approaches give little flexibility for adjusting point cloud
compression based on a-priori knowledge on the geometry of the scanned object. Furthermore, these methods
lead to suboptimal approximations if the 3D point cloud data is prone to noise.

In this talk we propose a variational method defined on finite weighted
graphs, which allows to sparsify a given 3D point cloud while giving the flexibility to control the appearance
of the resulting approximation based on the chosen regularization functional. The main idea of our approach
is a novel coarse-to-fine optimization scheme for point cloud sparsification, inspired by the efficiency of the Cut
Pursuit algorithm for total variation denoising. This strategy gives a substantial speed up in
computing sparse point clouds compared to a direct application on all points as done in previous works and renders variational methods now applicable for this task. We compare different
settings for our point cloud sparsification method both on unperturbed as well as noisy 3D point cloud data.