3
$\begingroup$

Suppose we have $N$ lines in general position (any two lines, but no three lines, meet at a point) ($N\geq 3$). Let the smallest bounded region have area $1$. Determine the minimum (or possibly infimum) of the total bounded area.

For example, $3$ lines create one triangular region while $4$ create one quadrangular region and two triangular regions (the complete region thus bounded is called a complete quadrilateral). I know that $N$ lines in general position will create ${N+1\choose 2}+1$ regions, ${N+1\choose 2}+1-2N=\frac{(N-1)(N-2)}{2}$ of those bounded on all sides by line segments, but I wanted to figure out how to make the regions maximally “equal” and how close it’s possible to get to the ideal minimum of $\frac{(N-1)(N-2)}{2}$ for a given $N$ (where all bounded regions have area $1$). I have little to no experience in the field of maximizing or minimizing geometrical quantities (especially in such a large mathematical space in which to minimize/maximize as this problem gives), so solving this is entirely beyond my experience.

It is easy to show that there is no maximal bounded area for $N\geq 4$ by drawing some three lines arbitrarily close to meeting at a point. In this case, the resulting triangular region becomes arbitrarily close to a point while maintaining an area of $1$ in the problem's scaling, and the area of the remaining regions grows arbitrarily large by comparison. But I really don't know how to do any of this when it comes to minimizing the total bounded area.

For $N=3$, with only one region, the minimum area is trivially $1$. For $N=4$, some fiddling around on Desmos has convinced me that the minimum area is indeed the ideal of $3$. For $N=5$, I believe that the minimum area still remains the ideal of $6$ (although here my fiddling around on Desmos gets much more nonrigorous and guesswork-y). For $N\geq 6$, however, any proofs or even good guesses of any sort elude me entirely.

If finding the exact minimum area (or infimum in case there’s somehow a minimum that can be approached but not actually reached, which I would not expect) is in fact too difficult to do well, I would also be interested in the growth rate of the actual minimal area relative to the ideal as $N\to\infty$. Also, I'm new to MO (my typical haven is MSE), so please feel free to correct me if I'm unclear/incorrect in any way or messed up/missed any tags or anything like that.

I originally posted this problem on Math Stack Exchange, but never received a solution. I then posed it to one of my math professors, but he dismissed it as seeming too hard and suggested I email it to a particular nother professor. I did, but haven't received a response yet and am pessimistic about the probability of a response at all. Incomplete ideas are welcome too. Thank you for your help!

Edit 1: The other professor did write back. He said this seemed like a problem in discrepancy theory, it does seem very hard or even impossible to do explicitly, and the next best thing would be to determine upper and lower bounds for the minimal area.

Edit 2: I wound up contacting Dr. János Pach (an expert in relevant fields) regarding the problem on the recommendation of my first professor. Apparently the problem (originally in a slightly different form) is a minor unsolved problem first posed by Fejes Tóth in 1987:

L. Fejes Tóth, On Spherical Tilings Generated by Great Circles, Geometriae Dedicata, 23 (1987), 67–71

And the only notable result on it since its posing comes from Dan Ismailescu in 2003:

D. Ismailescu, Slicing the pie. U.S.-Hungarian Workshops on Discrete Geometry and Convexity (Budapest, 1999/Auburn, AL, 2000). Discrete Comput. Geom. 30 (2003), no. 2, 263–276.

So certainly pretty darn hard. :)

$\endgroup$
5
  • 2
    $\begingroup$ I asked a not-entirely-unrelated question at the 1993 Western Number Theory Meeting; "(a) Let $n$ lines divide a disk into the maximum possible number of regions, namely ${n\choose0}+{n\choose1}+{n\choose2}$. How large can the smallest region be? (b) What is the largest number of equal-area regions a disk can be cut into by $n$ lines? A trivial lower bound is $2n$." I didn't get any answers. $\endgroup$ Commented Sep 9, 2022 at 0:02
  • $\begingroup$ ...well, that doesn't bode well for my problem. $\endgroup$ Commented Sep 9, 2022 at 5:07
  • $\begingroup$ I think regular stars are good candidates for minimizers, eg for $N=2n+1$ lines, I would place points at angles $2k\pi/N$ on the unit circle and connect point $k$ with point $k+n$. For $N=5$ this gives a pentagram, whose total area is $5+\sqrt{5}\simeq 7.236$ times its small triangles. This is bigger than the $6$ suggested in the post — what configuration with five lines gets an area less than this? $\endgroup$
    – user44143
    Commented Sep 10, 2022 at 16:34
  • $\begingroup$ @GerryMyerson, you liked the topic enough to ask a similar question at a conference (and remember it after 29 years!) but not enough to upvote the question here? $\endgroup$
    – user44143
    Commented Sep 10, 2022 at 17:21
  • $\begingroup$ Unfortunately, I don’t recall the particular arrangement I used- was it really over five months ago?- and my Desmos file doesn’t appear to have been saved. But either way, it’s absolutely possible my initial eyeballing was wrong- like I said, my work got much more guesswork-y at that point. $\endgroup$ Commented Sep 10, 2022 at 20:35

1 Answer 1

1
$\begingroup$

I wound up contacting Dr. János Pach (an expert in relevant fields) regarding the problem on the recommendation of my first professor. Apparently the problem (originally in a slightly different form) is a minor unsolved problem first posed by Fejes Tóth in 1987:

L. Fejes Tóth, On Spherical Tilings Generated by Great Circles, Geometriae Dedicata, 23 (1987), 67–71

And the only notable result on it since its posing comes from Dan Ismailescu in 2003:

D. Ismailescu, Slicing the pie. U.S.-Hungarian Workshops on Discrete Geometry and Convexity (Budapest, 1999/Auburn, AL, 2000). Discrete Comput. Geom. 30 (2003), no. 2, 263–276.

So certainly pretty darn hard. :)

$\endgroup$
2

You must log in to answer this question.

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