Certifying Smoothness of Discrete Functions and Measuring Legitimacy of Images.

摘要

Several problems that deal with smoothness of discrete functions and that are motivated by the task of deciding whether an N x N array of distances is a feasible laser radar (LADAR) image are investigated. The main observation is that there is a simple and explicit graph that is tightly related to the smoothness problem. The graph is used to show that a function can be verified to be Lipschitz on a random finite subset of R2 by testing the Lipschitz condition at only O(n) pairs of points. Keywords: Statistical models. (kr)