Inquiry on Optimal Placement of Smoke Detectors Using CGAL

[835700012]

Dear CGAL Discussion Group,

I am currently working on a project that involves the strategic placement of smoke detectors within a given space. Using half-edge data structures, I have successfully extracted a series of adjacent enclosed areas. The next step in my project requires the placement of smoke detectors in optimal positions to ensure maximum coverage with a minimal number of units.

Each smoke detector has a protective range that can be represented as a circle with a known radius, R. The objective is to cover as much of the enclosed areas as possible with as few circles as possible. This presents an interesting geometric problem, one that I believe the Computational Geometry Algorithms Library (CGAL) could help solve.

My requirement is to use circles of a fixed radius to cover as many irregular neighboring areas as possible. I am seeking an efficient method or algorithm within the CGAL suite that can assist in this task. Does CGAL offer a better approach or tool that can be used for optimizing the placement of fixed-radius circles to achieve maximum coverage of these areas?

Any suggestions or guidance on this would be greatly appreciated.

I am reaching out to inquire if there are existing algorithms or suggestions within the CGAL suite that could assist in determining the best locations for these detectors. Specifically, I am interested in algorithms that can help achieve the most efficient coverage of the enclosed areas, taking into account the fixed radius of influence for each detector.

Any guidance or recommendations on which parts of CGAL could be particularly useful for this problem would be greatly appreciated. I am also open to suggestions on alternative approaches or strategies that may be relevant to this scenario.

Thank you for your time and assistance.

Best regards,

From a new hand

[sloriot]

Maybe you can use the package https://doc.cgal.org/latest/Mesh_2 with a custom criteria where you refine faces if their circum-circles are larger than the radius of action. In the end, you can have one detector per region. This is definitely not optimal as you'll have a lot of triangles if the boundary domain has a lot of points (something that you can workaround maybe by using a polygon with less vertices that is including the original one), In any case, there is nothing out of the box that will give you the optimal solution.

[835700012]

In my case, a single detector (represented by a circle) might cover multiple areas, and it's not necessary to place a circle in each individual area. The shapes of these enclosed areas are fixed and cannot be changed. I am seeking an efficient method or algorithmthat could assist in optimizing the placement of these fixed-radius circles to achieve maximal coverage of the areas.