1

Suppose, that there is a Pizza which is round and has radius $1$. Now one would like to find the best way, under $n$ cuts, to cut the Pizza so as to obtain the minimum 'Microwave Oven Distance'-

  • For any point $p$ on the Pizza, its "microwave oven distance" $m(p, g)$ is defined as the minimum distance from $p$ to the edge of the piece $g$

  • After a cut, for each piece $g$ of the pizza, its "microwave oven distance" $m(g)$ is defined as the maximum "microwave oven distance" $m(p,g)$ of its each point $p$, i.e for any given piece $m(g) = \max(m(p,g))$ over all points $p$ on the piece

  • The cut's "Microwave Oven Distance" $m(c)$ is defined as the maximum of the individual distances for each piece

is there a way to find the best cut $c_n$ for a given $n$ and formula for $m(c_n)$?

achille hui
  • 122,701
athos
  • 5,177
  • 2
    Hi, I have edited for Question for better clarity, but you may want to define what exactly you mean by the 'edge' from which the distance is to be measured. Also, you might consider adding some context such as the significance of the problem, its source, why you find it interesting and what you tried to solve it. – user0 May 02 '19 at 09:09
  • This is missing a definition of cut. I assume they must be straight, because otherwise the goal can be optimised below any given value with a suitable spiral cut, but are they edge to edge, do they cut multiple pieces, and can the pieces be rearranged between each cut? – Peter Taylor May 02 '19 at 13:18
  • @PeterTaylor yes lines are straight. Let’s assume no rearranging – athos May 02 '19 at 13:19
  • Is the following an equivalent re-statement? Choose $n$ distinct chords of the circle. This cuts the circle into $k \ge n+1$ regions (pieces), each region bounded by the chords and the circumference, collectively called "edges". You want to minimize $\max_p \min_e distance(p,e)$ where $p$ is any point inside the circle and $e$ is any point on any edge (chord or circumference). Is this right? – antkam May 02 '19 at 14:56
  • @antkam yes this is a good restatement – athos May 02 '19 at 20:11

1 Answers1

2

Not a full answer (because I cannot prove it's optimal), and, this answer assumes the following interpretation:

A cut $c$ is a set of $n$ distinct chords of the circle. These chords cut the circle into $k≥n+1$ regions (pieces), each region bounded by the chords and the circumference, collectively called "edges". Then:

  • For any point $p$ in the circle (incl. interior), $m(p) := \min_{e \in \text{edges}} distance(p,e)$ is the shortest distance from $p$ to any point $e$ on any edge. (Note: It is obvious that the minimizing $e$ is on an edge bordering the region containing $p$, so this qualification does not need to be in the definition.)

  • We want to choose cut $c$ to minimize $m(c) := \max_{p \in \text{circle (incl. interior)}} m(p)$

Observation: For any region $g, m(g) := \max_{p \in g} m(p) =$ radius of the biggest circle that can be inscribed within $g$.

Reason: from any $p\in g$, a circle centered at $p$ lies entirely within $g$ iff its radius $\le m(p),$ by defintion of $m(p)$.

So we want a cut $c$ that minimizes the biggest inscribed circle, across all regions.

Conjecture: The best cut $c^*$ is simply cutting the pizza into parallel strips of width ${D\over n+1}$ where $D$ is the pizza diameter. In this case, for every region (strip), the biggest inscribed circle has radius ${D\over 2(n+1)}$ and so $m(c^*) = {D\over 2(n+1)}$.

I don't have a proof this is optimal. Any counter-example would need the following: Suppose cut $c'$ achieves $m(c') = \lambda < {D\over 2(n+1)}$. Since every point $p$ is within $\lambda$ of some edge, this means the entire circle is collectively covered by:

  • the ring-shaped region within $\lambda$ from the circumference, and

  • $n$ rectangular strips each of width $2\lambda$ and infinite length.

Since the ring-shaped region is fixed, this is equivalent to saying the "inner" circle of diameter $D-2\lambda$ must be covered by $n$ rectangular strips each of width $2\lambda$ and infinite length.

So my conjecture is equivalent to saying such a covering is impossible if $2n\lambda < D- 2 \lambda$.

antkam
  • 15,363