For a function defined on a convex set in a Euclidean space, midpoint convexity is the property requiring that the value of the function at the midpoint of any line segment is not greater than the average of its values at the endpoints of the segment. Under very mild assumptions, midpoint convexity is a well-known characterization of ordinary convexity. A discrete version of midpoint convexity is proposed here for functions defined on the integer lattice. A discrete midpoint point convex function is characterized by a discrete version of midpoint convexity where the value of the function at the (possibly noninteger) midpoint is replaced by the average of the function values at the integer round-up and round-down of the midpoint. We show that discrete midpoint convexity has nice theoretical and algorithmic properties, including (pseudo) polynomial-time minimization under appropriate assumptions. Furthermore, by restricting the distance between the endpoints in the discrete midpoint convexity definition, one obtains new classes of discretely convex functions and a unifying framework for several well-known notions of discrete convexity and for the notion of submodularity over the integer lattice.
Personal website of Fabio Tardella