Distributing points with respect to a concave function Suppose I have a concave function defined on the unit interval such that $f(0) = f(1) = 0$ and $\int_0^1 f(t) dt = \alpha$, where $\alpha$ is "small" (say $0.01$ or thereabouts).  Say I distribute $n$ points $x_1,\dots,x_n$ on the unit interval and consider the function $F(x_1,\dots,x_n) = \int_0^1 f(t) \cdot \min_i\{|x_i - t|\} dt$.  Is there a lower bound on $F$ as a function of $\alpha$ and $n$?  If $n=1$, I can show that a lower bound is $\alpha/6$, so I'm curious if something like $\alpha/(6n)$ holds in general.
 A: It seems that for large $n$ there will be an upper bound $c_n \alpha$ with $c_n$ asymptotic to $\frac{2}{9n}$ (and thus a bit better than the $\frac{1}{6n}$ suggested by the value of $c_1$).  The asymptotic equality condition should be: $f$ is a triangular function $\tau_z$ for some $z \in (0,1)$, defined by
$$
\tau_z(x) = \cases{
  x/z,& {\rm if}\phantom0x \leq z,\cr
  (1-x)/(1-t), & {\rm if}\phantom0 x \geq z
  }
$$
(i.e. $\tau_z$ is piecewise linear with a corner only at $x=z$ where $\tau_z$ attains its maximal value of $1$), and $x_1,\ldots,x_n$ are distributed on $(0,1)$ with density proportional to $\sqrt{f\phantom.}$ (which is probably not what most of us would have guessed at first).
The condition that $\alpha = \int_0^1 f(x) \phantom. dx$ be "small" is a red herring because the problem is linear in $f$, so that what works for small $\alpha$ works equally for all $\alpha$.  It is also enough to work with $f = \tau_z$ because the convex hull of functions $c \tau_z$ is precisely the concave functions $f$ on $[0,1]$ vanishing at the endpoints; e.g. if such $f$ has a continuous second derivative then
$f(x) = \int_{z=0}^1 (z-z^2) \phantom. (-f''(z)) \phantom. \tau_z(x) \phantom. dz$, and $-f''(z) \geq 0$ for $f$ concave.
Now the idea is that if $x_1,\ldots,x_n$ are regularly distributed with density $\delta(\cdot)$ on $[0,1]$ then $\min_i |x_i - t|$ behaves like $1/(4\delta(t))$, because it oscillates between $0$ and $1/(2\delta(t))$ like a nonnegative triangle wave.  The only restriction on $\delta$ is that it be a positive function with $\int_0^1 \delta(t) \phantom. dt = n$.  By Cauchy-Schwarz,
$$
\int_0^1 \frac{\tau_z(t)}{\delta(t)}dt \cdot \int_0^1 \delta(t) \phantom.dt \geq \left( \int_0^1 \sqrt{\tau_z(t)} \phantom. dt \right)^2,
$$
with equality iff $\delta^2$ is proportional to $\tau_z$.  Now we know $\int_0^1 \delta(t) \phantom. dt = n$, and compute $\int_0^1 \sqrt{\tau_z(t)} \phantom. dt = 2/3$ for all $z$.
Hence $\int_0^1  (\tau_z(t) / \delta(t)) \phantom. dt \geq \frac4{9n}$.  Since $\int_0^1 \tau_z(t) \phantom. dt = 1/2$, we deduce that
$$
\int_0^1 \frac{\tau_z(t)}{4\delta(t)}dt \geq \frac2{9n} \int_0^1 \tau_z(t) \phantom. dt,
$$
from which the claimed asymptotic should follow after some epsilon-chasing.
A: You can define the function $f(t)\cdot min_i|x_i-t|$ piecewise so that $f(t)\cdot min_i|x_i-t|=f(t)\cdot|x_i-t|$ when $t$ is on the interval $\left[\frac{x_{i-1}+x_i}{2},\frac{x_i+x_{i+1}}{2}\right]$.  Here we have to define $x_0=-x_1$ (so $\frac{x_{0}+x_1}{2}=0$) and $x_{n+1}=2-x_n$ (so $\frac{x_n+x_{n+1}}{2}=1$).  This makes the integral
\begin{equation}
F(x_1,...,x_n)=\sum_{i=1}^n\int_\frac{x_{i-1}+x_i}{2}^\frac{x_i+x_{i+1}}{2}f(t)\cdot|x_i-t|dt
\end{equation}
Now, $f$ isn't $0$ at the endpoints of these intervals and the intervals don't have length $1$, but they are concave and their average value is $\alpha/n$.  You can consider f on each interval as the limit of a sequence of concave functions defined on that interval which are each $0$ at the endpoints, so you should be able to put a lower bound on each integral in the same way that you did it for $\int_0^1f(t)\cdot|x_1-t|dt$.  I can't say what that lower bound might be, because I don't know how (or if) you used the length of the interval $[0,1]$ when you found the lower bound for $\int_0^1f(t)\cdot|x_1-t|dt$.  If you didn't use the length of the interval at all, the integrals will have to be on average greater than or equal to $\alpha/6n$, implying that $F(x_1,...,x_n)$ is bounded below by $\alpha/6$, which would be kind of interesting.  One more thing to note is that unlike your example when $n=1$, for the integrals in the sum above you have the additional condition that $f(x_i)$ is bounded away from $0$ by the value of $f$ at at least one of the endpoints of the intervals.  Maybe this will make it possible to put stricter lower bounds on each of these integrals.  I hope all that was clear (and correct). 
