# Least number of circles required to cover a continuous function on a closed interval.

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?

• 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.
– D.W.
Commented May 14 at 9:45
• 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 Commented May 14 at 15:29

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:
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:
But even that's not all: watch what happens when you put a circle through $$(\frac{1}{2}, \frac{1}{2})$$: