Maximum number of concave quadrilaterals in n points in regular position

Question

Consider N points in a plane. What is the maximum number of quadrilaterals that are concave? The minimum is always zero: form a convex polygon with all N points, and no 4 of the N will form a concave quadrilateral. But what is the maximum? I think it goes (based on my software):

N points,Max(Concave Quadrilaterals)

4,1

5,4

6,12

...

Is there an existing formula?

To be specific, here I am interested in all combinations of four points, so out of combin(N 4), what is the most that can be concave. So a triangle containing two points counts as two concave quadrilaterals.

I read as much as I could before asking, so, sorry if this is well known, I'm an amateur (actually hobbyist) mathematician at best. Thank you for this site, this is my first post after getting a lot out of it.

Answer 1

This is more of a long commentary on the question.

This is a very interesting question, thank you OP. This is a revised version of my answer.

Perhaps the question can be reworded this way.

Let $N$ be a positive integer. If $X$ be a set of points in the plane that $|X|=N$ and no three of which lie on the same line, then denote by $c_N(X)$ the number of fours of $X$ whose convex hull is a triangle. What is the maximal value of $c_N(X)$?

This problem can also be reformulated as follows.

For a given integer $N$, find the maximum possible integer $\bar{c}_N$ such that any set of $N$ points in the plane in general position has at least $\bar{c}_N$ convex quadrilaterals.

It is clear that $$c_N+\bar{c}_N=\binom{N}{4}.$$

Further, we can observe that the number of convex quadrilaterals on the set $X$ of points in the plane in general position is equal to the number of crossings of the edges of the complete graph on the set $X$ if its edges are rectilinear.

Therefore the convex quadrilateral problem is equivalent to the following problem.

Find the rectilinear crossing number of the complete graph $K_N$, i.e., to determine the minimum number of crossings in a drawing of $K_N$ in the plane with straight edges and the nodes in general position.

We denote this number by the symbol $\bar{v}(K_N)$. We see that $\bar{c}_N=\bar{v}(K_N)$.

It turns out to be a pretty old problem. Here are some first values $\bar{c}_N=1,3,9,19,\ldots$ for $N=5,6,7,8\ldots$ (OEIS A014540). Quite a few values are known for small $N$ see here

To illustrate what we have said, here is one picture.

On the left is the configuration $X$ of $5$ points, for which $\bar{v}(K_5)=\bar{c}_5(X)=1$.

The configuration $X$ of $6$ points is shown on the right, for which $\bar{v}(K_6)=\bar{c}_6(X)=3$.