19
$\begingroup$

Consider the square $[0,1]^2$. Assume that this region is divided into $N=K^2$ equispaced grid points. How many convex curves can be drawn in terms of $K$?

The points $(0,1)$ and $(1,0)$ are known to be on the convex curve. I am interested in the answer of this questions due to two reasons:

$1.$ I would like to consider $K\rightarrow \infty$ and compare the total number of convex functions to the total number of other types of functions for example (decreasing, etc.)

$2.$ Later I would like to write a program to realize all such discrete convex functions in order to perform optimization over all these functions (for a specific $K$).

I would be also happy to hear any ideas about how to realize this algorithmically.

Here is an example, where one can see examples of three different convex functions:

enter image description here

In this example there are altogether $N=121$ grid points and the distance between each neighboring pair of grid points both in $x$ and $y$ direction is $0.1$.

So, for every value on the $x$ axis, there will be a corresponding value on the $y$ axis.

ADDED (15.07.2018): I programmed and obtained the grid. Using this approach it is impossible to get all convex functions as $N\rightarrow \infty$. I bet we are not even near. Consider the convex function which linearly decreases from $(0,1)$ to $(0.4,0.2)$ and again linearly decreases from $(0.4,0.2)$ to $(1,0)$. It is impossible to get this function with this approach. No mater how fine the grid is, there are infinitely many other functions which are not achieved.

$\endgroup$
15
  • 1
    $\begingroup$ Can you provide some positive and negative examples of such functions? Or even better a drawing? $\endgroup$ Jun 17, 2018 at 19:28
  • 1
    $\begingroup$ yes I can. Just a second please. I also forgot that $(0,1)$ and $(1,0)$ should be on the convex function. $\endgroup$ Jun 17, 2018 at 20:08
  • $\begingroup$ The function in your diagram does not appear to be convex; the curve bends down at $(0.3, 0.5)$. $\endgroup$ Jun 19, 2018 at 15:48
  • $\begingroup$ (Oh, and you have $121$ grid points rather than $100$). $\endgroup$ Jun 19, 2018 at 15:49
  • $\begingroup$ @HenningMakholm you are right. so just a fast illustration without any care about anything. Let $(0.2,0.5)$ and $(0.3,0.4)$ be the related points. As you can see, my drawing is also horrible:) $\endgroup$ Jun 19, 2018 at 15:52

1 Answer 1

10
+50
$\begingroup$

I am not sure that this is what you want, but here is my thinking about it:

If $n$ is the number of divisions of unity ($n=10$ in your drawing), and $x_i, i=1,2,\ldots n$ is the number of divisions traveled downwards by each segment of your curve (for the green curve $x_1,\ldots ,x_{10}$ would be $5,2,1,1,1,0,0,0,0,0$), then your problem could be formulated as the number of solutions of the following integer equation:

$x_1+x_2+\ldots+x_n=n$

subject to:

$x_1\ge x_2\ge\ldots\ge x_n\ge 0$

We can observe that each solution of this integer equation can be put in $1:1$ correspondence with a partition of $n$ (by ignoring the zeros). For the green line, this is:

$10=5+2+1+1+1$

So the number of convex functions equals $p(n)$, which is the number of partitions of $n$.

Unfortunately, $p(n)$ does not have a nice closed-form formula, but you can see the Wikipedia page Partition_(number_theory) for more details, recurrences, asymptotics, etc.

EDIT: To address OP's question about comparing $p(n)$ with the number of non-increasing functions:

If $q(n)$ is the number of non-increasing functions (not necessarily convex), then by reusing the previous notation, we get that $q(n)$ is the number of integer solutions of the following equation:

$x_1+x_2+\ldots+x_n=n$

subject to:

$x_1, x_2,\ldots, x_n\ge 0$

This is a classic Stars and bars problem (theorem two), whose solution is:

$q(n)= {n + n - 1 \choose n - 1}={2n-1\choose n-1}$

A quick check on Wolfram Alpha shows that $\frac{q(n)}{p(n)}\to\infty$, so $p(n)=o(q(n))$

$\endgroup$
8
  • $\begingroup$ It would be nice to come up with a recursive formula to count them in exponential time. And I think it should be able to reduce it to a polynomial in time solution using dynamic programming. $\endgroup$
    – Hashimoto
    Jul 3, 2018 at 4:26
  • $\begingroup$ How would you represent a curve consisting of two straight lines, going from $(0,1)$ to $(0.3,0.3)$ and then to $(1,0)$? $\endgroup$ Jul 4, 2018 at 14:01
  • $\begingroup$ @Hashimoto the recursive formula can be found in the Wikipedia link referenced above or Wolfram MathWorld (see (11) and (20)). However, the asymptotic formula is $p(n)\sim\frac{1}{4n\sqrt{3}}e^{\pi\sqrt{2n/3}}$, which suggests that OP's question 2 is pretty much hopeless (generating all partitions and optimization by brute force) $\endgroup$
    – Momo
    Jul 4, 2018 at 22:58
  • $\begingroup$ @Peter Košinár I have only considered the lines which pass through each division of the grid, as illustrated in OP's picture. $\endgroup$
    – Momo
    Jul 4, 2018 at 23:03
  • $\begingroup$ Would you mind addressing the issue of comparison between the total number of all increasing functions to the only convex ones over the same grid approach? $\endgroup$ Jul 5, 2018 at 21:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .