I have a square plate of size 1x1, full of lots of skittles. I want to eat all of the skittles, but the only way I can get the skittles is through these two oracles:
$f(x, y, r)$ tells me how many skittles are in the circle of radius $r$ centered about the point $(x,y)$ on my plate
$q(x, y, r)$ gives me all of the skittles that are in the circle of radius $r$ centered about the point $(x,y)$ on my plate
However, my plate is very big, and my oracles are very small. So the $r$ given to $f$ and $q$ must be less than or equal to a given value $R$.
Oracles don't come free these days: I have to pay a cost of 1 each time I call $f$. Each time I call $q(x, y, r)$, I must pay a cost of $f(x, y, r)/P$: 1 for each $P$ skittles that my oracle brings to me (rounded up). The $P$ is an input to this problem. Then those skittles are eaten.
There are $N$ skittles on my plate. What is a strategy that doesn't cost very much to eat all of my skittles, in terms of $N, R$, and $P$?
I'm curious about two cases:
- If an adversary is placing skittles, what is the most they can make me pay?
- If all the skittles are each independently placed according to a uniform distribution over the entire plate, what is a strategy that does "sorta well", and what is the expected amount I would need to pay?