2
$\begingroup$

I am working on a project, in which I have to optimize the placement of N unequal circles in a given rectangular area, such that if these circles are considered as a sensor field, I can possibly reduce the points from where intrusions are possible.

The total area of N unequal circles is not fixed with respect to the given rectangle, i.e. combined area of circles can be less or approximately equal to the area of the rectangle.

So, basically I have to create a particular optimised configuration where there are minimal voids and intrusions. I need an algorithm to implement this, such that I get relative coordinates of circles in such an optimal configuration.

$\endgroup$
0
$\begingroup$

I don't know how to maximize the area covered. However the following is an approximation. Put a grid of points on top of the rectangle. Then maximize the number of points covered by at least one sensor. Assume we have given set of sensors each with a given radius. Then we can formulate a Mixed Integer Quadratically Constrained Programming (MIQCP) problem as follows:

enter image description here

Solvers like Cplex and Gurobi handle these type of problems. The results for some invented small data can look like:

enter image description here

$\endgroup$

Your Answer

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

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