Partitioning a square for optimal queries

Question

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:

1. If an adversary is placing skittles, what is the most they can make me pay?
2. 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?

Answer 1

A good idea seems to be to use nonoverlapping circles in the densest circle packing in 2d. Please check the corresponding Wiki-page: https://en.wikipedia.org/wiki/Circle_packing. This way you reach up to $C = 0.907$ coverage. Assuming the scittles are uniformly distributed and $N \gg \frac{1}{S_c}$, where $S_c$ is the surface of the cricles you use, we may estimate that you'll have to pay $\frac{CN\#circles}{P} = C^2N/S_cP$ for fetching and roughly $\#circles = C/S_c$ for looking in thustly covered area. We may cover the gaps, which cover about $1-C$ of the square, by correspondingly smaller cirlces again, the cost of looking should be just as before. The cost of fetching is hard to estimate, without delving into geometry to much at this point, but i guess it may be roughly $(1-C)N/P$. Also, you may terminate one you reach $N$.

A smart adversary would start placing the scittles in the gaps. I assume it's a good idea to pick a random reference for the lattice of circle placing. Also you could randomly pick the areas to check for scittles from the main lattice (covering $C$) and from the minor lattice (covering $1-C$).

Now we are stuck with the decission which radius to pick in $[0,R]$. I assume as large as possible under the placed constrains makes sense. There is probably space for optimization by choosing some radius $r$ so that your main lattice has little overflow over your plate.

Alternatively you may use the densest packing, but with circles overlapping. This way all the gaps vanish and you skip the cost for lookups on the secondary lattice.

Hope this input helps you somewhat.

Answer 2

-I think ur plate (geometrically) will have a fixed no. of circles of max. radius R that needs to be checked no matter how or where did you start; So let us assume this number is X (= 1/(⚻R^2)) .... {if u divide ur plate to 1/R^2 squares and thus adjacent circles u'll miss tiny small places bet. the circles that may contain skittles} . - So, u have to loop from 1 to X checking every circle & counting skittles till N is reached; to make it faster in average u may start from the center of the plate moving to the border . -If an adversary is placing skittles, that's another story because each circle may be visited more than once, and the idea would be to follow his movement checking the circle surrounding it