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.

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

Your Answer

Jay Hurley is a new contributor. Be nice, and check out our Code of Conduct.

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.