Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

I Smoothness of Discrete Functions

  1. Jul 4, 2016 #1
    Hi Physics Forums

    Is there a specific technique to measure how smooth a discrete function is?

    By smooth I mean that if you change the input by a minimum amount then you know that the objective function result will not have a big jump.

    For example The Closest String Problem is completely smooth function, since if you change the input string by only one letter, then the distance to the furthest string will change by at most one.

    The Traveling Salesman Problem is also smooth, but not completely so. If you change only the order that you visit two cities then the total distance traveled could not change as much as if you altered more. However there could be larger and smaller jumps.

    Moving around a grid of random numbers would be completely unsmooth.

    I'm sure there must be another word for this phenomena and some research done already. But google is providing anything except "smoothing discrete functions" which is a completely different thing altogether!
  2. jcsd
  3. Jul 4, 2016 #2

    Stephen Tashi

    User Avatar
    Science Advisor

    It isn't clear what you have in mind for the domain of the function - one real variable ?, a vector of variables ?

    If you want to look at methods that are analogous to those used for differentiable functions (e.g. first derivative being bounded or partial derivatives being bounded) investigate "the calculus of finite differences".
  4. Jul 4, 2016 #3


    User Avatar
    Science Advisor

    The only thing I can recall is a function is from actuarial science: Barnett n-th order smooth iff ##|{\Delta^n a_x}| \cdot 7^n < a_x##. But this is really for life tables.
  5. Sep 7, 2016 #4
    A discrete function is smooth if f(2n) = Θ(n) (theta of n). If f(2n) = o(n), it is not smooth. Source: Algorithms by Neapolitan, Appendix B.2.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted