1

I have a collections of map points (about 500 thousand, on an UTM grid if it matters), each of which has a non-negative weight, and I would like to find the circle with some fixed radius r that contains the largest total weight of points. An obvious first approximation to the problem is to buffer every point to the appropriate radius, find all points contained in that circle and sum their weights and returning the maximum; but it's also easy to construct instances where this approach fails to find the optimal solution.

So I'm wondering if this is a problem that can be tractably solved to find the optimal circle? My gut feeling is that it's probably intractable, but my geometry skills aren't good enough to make much headway in any direction. But it also feels like the kind of problem that already has a name and an accepted answer, I just don't know how to find it.

Improve this question
1
  • Have your considered a heat map with a uniform kernel?
    – JGH
    Commented Sep 3 at 12:58

1 Answer 1

Reset to default
-1

A colleague I had previously discussed this with just found this paper, which seems to give an O(n^2) solution to the problem!

Improve this answer
3
  • 2
    Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center.
    – Community Bot
    Commented Sep 2 at 12:39
  • Link-only answers are always vulnerable to link rot. Any Answer which refers to another post must summarize the content of that post, so that, if the link dies, the Answer is not irreparably damaged.
    – Vince
    Commented Sep 3 at 2:12
  • Yeah, I'll try to summarize, but first I'll have to read (and understand) the paper.
    – arnsholt
    Commented Sep 3 at 8:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.