To reduce the cost of storing, processing and visualizing a large-scale point cloud, we propose a randomized resampling strategy that selects a representative subset of points while preserving application-dependent features. The strategy is based on graphs, which can represent underlying surfaces and lend themselves well to efficient computation. We use a general feature-extraction operator to represent application-dependent features and propose a general reconstruction error to evaluate the quality of resampling; by minimizing the error, we obtain a general form of optimal resampling distribution. The proposed resampling distribution is guaranteed to be shift-, rotation- and scale-invariant in the 3D space. We then specify the featureextraction operator to be a graph filter and study specific resampling strategies based on allpass, lowpass, highpass graph filtering and graph filter banks. We validate the proposed methods on three applications: large-scale visualization, accurate registration and robust shape modeling demonstrating the effectiveness and efficiency of the proposed resampling methods.