# Maximum number of concave quadrilaterals in n points in regular position

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):

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.

New contributor
Jay Hurley is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
• It is fundamental that you say how you work. Is it by simulation, by spreading random points in the plane ? In this case, extreme caution is necessary. Have you heard about random normal distributions or considered working in the unit square $[0,1] \times [0,1]$ ? It can give very different results. Nov 23 at 12:48
• Why concave polygons more than convex ones or self-crossing ones ? Nov 23 at 13:05

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$$.

• I agree but this accounts for events with probability $0$. A more fundamental issue is what I have attempted to explain in my comment. Nov 23 at 12:44