2
$\begingroup$

Given: I have 2D non-parametric formula that provides instantaneous intensity at certain (x,y) location.

Required: I want to en-circle a region where the density is high via optimization. In other words fitting a circle whose radius must be optimized such that the density is maximum at certain region.

Analogy: Consider an oil spill in water (assume stationary). I want to find an area enclosed inside a circle that constitutes highest density. It is to identify most important spots that require cleaning fast. So less dense area is not cleaned first.

The density can be computed by performing monte-carlo integration of the intensity values inside the a circle (size of which has to be optimized) and then dividing by the area of the circle. So if the size of circle grows so is its area. The outcome of optimization is the value of the radius of the circle and its position.

Question: Now considering the area is huge, and the problem cannot be solved analytically, what are some of the approaches/heuristics that I can use to solve the problem?

Improve this question
$\endgroup$
11
  • $\begingroup$ If the analogy to an oil spill is taken fairly literally (e.g. there is a source from which these intensity values have flowed and you now have a snapshot of these values), it may be help to find a maximum of the intensity first as the origin of your circle. From there, you could incrementally increase the radius until the density stops increasing. $\endgroup$ – Tyberius May 19 '20 at 19:24
  • 4
    $\begingroup$ You seem to be missing a "trade-off" variable, either in your objective function or constraints. By making the circle radius infinitesimally small, centered at the point of highest intensity, you get highest density, but little total capture. $\endgroup$ – Mark L. Stone May 19 '20 at 20:06
  • 1
    $\begingroup$ @Tyberius this is exactly what I thought initially, I could simply "anchor" the center by solving this $$\textrm{argmax}I(x,y)$$ then, then once the circled is anchored at certain (x,y) simply solve for $$\textrm{max}\frac{\Sigma I(x,y)}{\pi \|x,y\|} $$ and get the maximum density. The problem with this is that if there are instantaneous peaks in the intensity value that gradually decreases then it wont work or compared to something that is possibly not peaky at all but consistant in intensity. $\endgroup$ – gfdsal May 19 '20 at 21:06
  • 1
    $\begingroup$ @gfdsal Thanks, the revised question is much clearer. I'll delete my comments, and if you want, you can delete your replies too. $\endgroup$ – LarrySnyder610♦ May 19 '20 at 21:06
  • 1
    $\begingroup$ Do you really want to locate a circle of some fixed radius, such that the integrated density is maximized? To optimize a trade-off, you could jointly optimize center and radius of circle, by maximizing integrated density minus a cost, where the cost might be proportional to radius squared (or whatever suits your fancy). And what do you mean by non-parametric 'formula"? Given a point (x,y), what is involved in evaluating the density there? $\endgroup$ – Mark L. Stone May 19 '20 at 21:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.