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$
  • 1
    $\begingroup$ Can you provide some positive and negative examples of such functions? Or even better a drawing? $\endgroup$ – Jsevillamol Jun 17 '18 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$ – Seyhmus Güngören Jun 17 '18 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$ – Henning Makholm Jun 19 '18 at 15:48
  • $\begingroup$ (Oh, and you have $121$ grid points rather than $100$). $\endgroup$ – Henning Makholm Jun 19 '18 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$ – Seyhmus Güngören Jun 19 '18 at 15:52
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$
  • $\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 '18 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$ – Peter Košinár Jul 4 '18 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 '18 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 '18 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$ – Seyhmus Güngören Jul 5 '18 at 21:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.