3

We understand that the number of triangles possible is given by kC3, since any selection of 3 points uniquely determine a triangle.

This is not true for quadrilaterals though, since for selections where 1 of the points lie within the other 3, we can obtain 3 quadrilaterals. The value kC4 merely gives us a lower bound, which occurs whenever all k points lie on a circle (or whenever none of the k points lie within any possible triangle, but this condition is guaranteed by a placing them on a circle).

Now, my question is: what is the upper bound on the number of quadrilaterals we may form? Under what configuration of the k points will this value be the actual answer? Even more generally, is there an explicit formula in k and n giving us the upper bound for an n-gon and is there a rule which will help us determine how these k points should be placed?

Thank you in advance.

hoogepooge
  • 31
  • How about the case where the points are collinear? Do we count degenerate quadrilaterals? – Calvin Lin Aug 11 '13 at 06:38
  • @AndréNicolas: It's a little unclear, but I think the question is counting the number of simple quadrilaterals. In order to maximize this number, one wants to minimize the number of convex quadrilaterals. The circle is an upper bound for convex quads, so it's a lower bound for simple quads. – Chris Culter Aug 11 '13 at 07:15
  • @ChrisCutler I don't think the OP is ruling out convex quadrilaterals, since he/she specifically says the case of one point inside the triangle formed by the others gives three quadrilaterals. (This is why $_kC_4$ is said to be a lower bound.) – coffeemath Aug 11 '13 at 07:53
  • 1
    @coffeemath That's not my name. :) Anyway, I don't assume that convex quads are ruled out. Any four points contribute either one convex, simple quad or three non-convex, simple quads. This is consistent with OP's counting in the second paragraph. – Chris Culter Aug 11 '13 at 08:10

1 Answers1

2

Your question is equivalent to determining the rectilinear crossing number of the complete graph on $k$ vertices. This is an open problem! I don't know much about it, so I'll refer you to a survey article from 2011: http://www.csun.edu/~ba70714/survey.pdf

Edit: Here's the explicit connection. For every four vertices, consider the three pairs of rectilinear edges between them. Either exactly one pair crosses, in which case there is only one simple quad that passes through the vertices, or no pairs cross, in which case there are three simple quads that pass through the vertices. So if there are $c$ crossings, then the number of simple quads is $$3\binom k4-2c.$$

For example, the rectilinear crossing number of $K_6$ is $3$, so the maximum number of simple quads formed by $6$ points is $$3\binom 64-2\times3 = 45-6=39.$$

Here's a drawing of $K_6$ with only $3$ crossings, which I stole from this PDF:

Rectilinear realization of complete graph on 6 vertices with 3 crossings

I guess if you're patient enough, you can actually count $39$ simple quads in there. I haven't tried this myself. :)

Chris Culter
  • 26,806
  • What does this crossing number approach imply for the case $k=6$? Using the circle approach of the OP gives 15 quadrilaterals, while using a regular 5-gon together with its center gives 25. Concretely, given the crossing number of $K_6$, how is the upper bound on the number of quadrilaterals computed? – coffeemath Aug 11 '13 at 07:49
  • @coffeemath I've updated the answer with details. Please let me know if something remains unclear! – Chris Culter Aug 11 '13 at 08:08
  • Wow, Chris! This is some really fascinating stuff! I am completely foreign to this graph theory thing, but I believe I caught on.

    If I am not mistaken, this crossing number gives the lowest possible number of intersections when we draw the complete graph? Is there a particular way to determine how the vertices should be placed such that we obtain this number?

     – hoogepooge Aug 11 '13 at 08:22
  • Chris Culter (spelled OK this time): Thanks for the explanation. I don't see how to actually get 39 quadrilaterals from 6 vertices; maybe that graph is complicated! +1 – coffeemath Aug 11 '13 at 08:23
  • @coffeemath It's a little complicated, yeah! I just added a diagram to my answer. I got it from Google, although in retrospect, it seems like the kind of thing one could figure out eventually. – Chris Culter Aug 11 '13 at 08:34
  • @hoogepooge I don't know if there's a way to determine how the vertices should be placed. Since the problem is unsolved in general, I suspect that there isn't a single method that achieves the best number for every $k$. However, there might be some general heuristics that always apply, and there might be arrangements that are simple but slightly sub-optimal. After all, there are known asymptotic bounds, which had to be proven somehow... But I'm just guessing at this point. If you read the 2011 survey, you'll know much more about the problem than I do! – Chris Culter Aug 11 '13 at 08:39
  • Gee, thanks for the effort Chris, I just verified for myself that there are indeed 39 possible quads in that diagram. Have a nice day ahead! – hoogepooge Aug 11 '13 at 08:42