7
$\begingroup$

The Circle Division by Lines problem (link) asks into how many regions, at most, one can divide a circle (or: the plane) with $n$ chords (or: lines).

I am wondering about a similar question, but for which the dividing curves are not chords/lines, but rather $\mathsf{V}$-shaped curves, which can be oriented in any direction. Stated succinctly:

What is the maximum number of pieces in which it is possible to divide a circle for a given number of $\mathsf{V}$-shaped cuts, where the cuts can be oriented in any direction?


RE: Initial Comments I am fine with the assumption that the vertex must be inside the circle and the angle should be fixed across all $\mathsf{V}$-cuts. But, I am open to suggestions as others see fit!

RE: Solution In fact, the formula provided works irrespective of the vertex angle. In retrospect, Euler's Formula is a wise way to solve the problem and, with a quick check, one finds that plugging in $n=1$ and $n=2$, respectively, yields $2(1)^2 - 1 + 1 = \fbox{2}$ and $2(2)^2 - 2 + 1 = \fbox{7}$, as desired.


For example, when there are a total of $2$ $\mathsf{V}$-cuts, I believe the maximum is $7$ regions:

enter image description here

What is the maximum number of regions for $n \in \mathbb{Z}^+$ total $\mathsf{V}$-cuts?

$\endgroup$
  • $\begingroup$ $n=1 \implies R=2$ and $n=2 \implies R=7$. If we have enough terms, maybe we can observe a recurrence relationship? $\endgroup$ – Mohammad Zuhair Khan May 14 at 15:52
  • $\begingroup$ @MohammadZuhairKhan Approaching this with small cases and looking for a pattern seems like a potentially wise heuristic to me. That is certainly how I broach the circle-chord problem when teaching it. But, I am not sure how to assert with confidence in the case of e.g. $n=4$ that the maximum is achieved. (Maybe there is a way to come up with a meaningful upper bound?) In other words: I'm not quite sure how to generate terms! $\endgroup$ – Benjamin Dickman May 14 at 15:57
  • 2
    $\begingroup$ You can produce more regions if the cuts are allowed to touch the edge or have the tip of the $V$ outside of the circle. $\endgroup$ – Vasya May 14 at 15:57
  • 3
    $\begingroup$ Does the vertex of the V have to be inside the circle? If not, you can have $3$ regions for $n=1$ and $9$ for $n=2$. $\endgroup$ – Robert Israel May 14 at 15:58
  • 1
    $\begingroup$ @RobertIsrael The version with the vertex inside the circle and the angle fixed might be the easiest to broach, first, but I am open to modifications. Do you have a suggestion either way? $\endgroup$ – Benjamin Dickman May 14 at 16:02
2
+50
$\begingroup$

We consider a simple case when vertices of $\vee$-cuts must be inside the circle, but their angles can be the same or differ (it turns out, that this doesn’t change the answer). A configuration of $\vee$-cuts can be naturally considered as a planar connected (multi)graph. Let $0\le V_{ij}\le 4$ be the number of intersection points between $i$-th and $j$-th $\vee$’s. Put $S=\frac 12\sum_{i\ne j} V_{ij}\le 2n(n-1).$ It is easy to see that the graph has $$V=2n+\tfrac 12\sum_{i\ne j} V_{ij}=2n+S$$ vertices and $$E=2n+\sum_{i}\left(1+\sum_{j\ne i}V_{ij}\right)=3n+2S$$ edges. By Euler’s formula, the graph $G$ has

$$F=1+E-V=1+3n+2S-2n-S=1+n+S\le 2n^2-n+1$$

inner faces and the equality is attained iff each $V_{ij}$ equals $4$.

$\endgroup$
  • 2
    $\begingroup$ I think you meant $E= 2n+\sum_i\left(1+\sum_{j\neq i}V_{ij}\right)$? Also, your wording kinda hints at it, but configurations in which $V_{ij}$ is $4$ for all pairs $i,j$ can be built, so that bound is tight. $\endgroup$ – N.Bach May 18 at 8:06
  • 1
    $\begingroup$ @N.Bach Yes, you are right. Thanks. $\endgroup$ – Alex Ravsky May 18 at 9:29
  • 1
    $\begingroup$ Euler's Formula is a great idea in retrospect; this is nice, thank you! $\endgroup$ – Benjamin Dickman May 18 at 16:00

Your Answer

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.