6
$\begingroup$

Question: Given a planar region $R$ of unit area and an integer $n$, to cut $n$ circular disks (their sizes need not be equal) such that the highest fraction of $R$ is taken off.

A simple greedy algorithm would be to repeatedly cut the biggest disk that can be cut at each stage from what remains of $R$. I don't know of any $R$ and $n$ where this algorithm clearly fails to give an optimal result. Ideally, one is looking for a convex $R$ and some $n$ such that the greedy algorithm clearly fails.

Remarks: If from a given $R$, instead of disks, $n$ triangles or $n$ squares are to be cut such that max fraction of $R$ is to be removed, 'greedy' clearly fails in general. For simple examples, see R.Nandakumar's blog.

One can ask whether the problem of cutting say $n$ triangles off from a unit area $m$-gon is NP complete.

Note (18th Jan, 2021): One can also ask about covering a given $R$ with a specified number of disks (which could be of different sizes) such that the least portion of the covering disks go waste - and with say, squares instead of disks.

Improve this question
$\endgroup$
4
  • 6
    $\begingroup$ 3 circles, touching, arranged in a triangle, then take $R$ the convex hull scaled to area 1 and $n=3$? $\endgroup$
    – J.J. Green
    Commented Dec 30, 2020 at 15:12
  • $\begingroup$ yes, checked it! that was a possibility that I had overlooked. Thanks! $\endgroup$
    – Nandakumar R
    Commented Dec 30, 2020 at 18:32
  • $\begingroup$ This question is closely related: mathoverflow.net/q/115455 $\endgroup$
    – Anton Petrunin
    Commented Dec 31, 2020 at 6:38
  • 2
    $\begingroup$ A slightly better version, 3 discs radius $1$, $1+\epsilon$, $1$ with centres at $(-1, 0)$, $(0,0)$, $(1,0)$ and $R$ the convex hull of these. The greedy algorithm will choose the centre disk first, then a radius $(1-\epsilon)/2$ disc, compare this to the pair of outer discs. For $\epsilon = 0$, $R$ has area $\pi + 4$, the "greedy selection" (which the greedy algorithm might not choose for $\epsilon=0$) is $5\pi/4$, the outer selection is $2\pi$. Let $\epsilon \rightarrow 0$ for inequalities with these values as bounds in the greedy case. $\endgroup$
    – J.J. Green
    Commented Dec 31, 2020 at 12:10

0

Reset to default

You must log in to answer this question.