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$

1 Answer 1

Reset to default
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$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.