7
$\begingroup$

Now asked on MO here.

This question is a generalisation of a prior question. Given a continuous function $f :[a,b]\to\mathbb{R}$, what is the least number of circles with radius $r$ required to cover the graph of $f$?

It is easy to prove (by using the extreme value theorem) that only finitely many circles are required to cover the graph of $f$.

But how can I find the least number of circles? I don't think a closed form exists (I also think Fourier series might be a part of the solution to this problem but I couldn't reach am algorithm using it), but is there another solution, like an indefinite integral? If there isn't, is there an algorithm that can solve this problem?

$\endgroup$
3
  • 1
    $\begingroup$ There is a natural greedy algorithm you could try: find the largest $a'$ such that a single circle can cover the graph of $f$ on $[a,a']$; then update $a$ to the value $a'$ and repeat. However I suspect it is not correct. See cs.stackexchange.com/q/59964/755. Perhaps you might like to construct a counterexample for yourself, and explore whether you can think of any way to fix it, perhaps using dynamic programming. $\endgroup$
    – D.W.
    Commented May 14 at 9:45
  • 1
    $\begingroup$ Clearly it can be made arbitrarily large by choosing a function which peaks very high in the interval. If the range extends from $0$ to $k$ you need at least $k/(2r)$ circles $\endgroup$
    – Ross Millikan
    Commented May 14 at 15:29
  • 1
    $\begingroup$ Thanks a lot for the bounty, I was not expecting this. $\endgroup$
    – Dominique
    Commented yesterday

1 Answer 1

Reset to default
8
+100
$\begingroup$

This is not an answer to your question, merely a way to indicate how difficult this might be. Imagine the following function: $f : [0,1] \to \mathbb{R} : x \mapsto 4(x-x^2)$ and $r=\frac{4}{5}$ (or $0.8$).

First, you might think the solution being $3$: you start by a circle in $(0,0)$ , you also have a circle in $(\frac{1}{2}, 1)$ and a last (third) circle in $(1,0)$, which gives the following drawing:

enter image description here

However, there's a solution with just two circles: one in $(\frac{1}{2}, 0)$ and a last (second) circle in $(\frac{1}{2}, 1)$, as you can see in following drawing:

enter image description here

But even that's not all: watch what happens when you put a circle through $(\frac{1}{2}, \frac{1}{2})$:

enter image description here

Good luck finding a general solution :-)

$\endgroup$

You must log in to answer this question.

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