Maximize colors within a circle

35 Views Asked by At

I have a set of $m$ points $P$ over a large bidimensional space, each point having a color. Every color belongs to one of $n$ disjunct sets $S_i$ of colors. Given a circle $c$ we define $C_c$ as the set of colors within the circle $c$ and $$g_i(c) = \frac{|C_c\cap S_i|}{|S_i|}$$

I want to find a center for a circle with a fixed radius $r$ that maximizes the function $$f(c) = \prod_{i=1}^n g_i(c)$$

I've found similar problems but none quite the same. The Weber problem seems closely related but it differs in many ways. Cluster analysis also seems related though I haven't identified any model that might help me. There's Focal Analysis on GIS but it's not quite the same and doesn't look like a good fit for the sparsity of the data.

A couple of brute force approaches that work are using Angular Sweep algorithm or building a KDTree and finding the $r$-nearest neighbors but in both cases I'd be recomputing $f$ without benefit of previous computations.

It feels like something like a Quad tree could store partial results, and I keep returning to algorithms related to Voronoi tesselation. For instance, Fortune's algorithm seems like a practical way of reusing previous results.

Is this a known problem? If it is, what it is called? Otherwise, are there closely related problems or generalized algorithms that cover it?