3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Jean Marie
    Nov 23, 2022 at 12:48
  • $\begingroup$ Why concave polygons more than convex ones or self-crossing ones ? $\endgroup$
    – Jean Marie
    Nov 23, 2022 at 13:05

1 Answer 1

1
$\begingroup$

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.

enter image description here

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

$\endgroup$
1
  • $\begingroup$ I agree but this accounts for events with probability $0$. A more fundamental issue is what I have attempted to explain in my comment. $\endgroup$
    – Jean Marie
    Nov 23, 2022 at 12:44

You must log in to answer this question.

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