Repulsion-Based p-Dispersion with Distance Constraints in Non-Convex Polygons

Area of Science:

• Computational geometry
• Operations research
• Optimization algorithms

Background:

• The p-dispersion problem aims to maximize circle radii within a given area.
• Existing methods are limited to simple geometric shapes due to NP-completeness.
• Optimal facility placement is a key real-world application.

Purpose of the Study:

• To develop a computationally feasible suboptimal approach for the p-dispersion problem in non-convex polygons.
• To adapt the method for solutions with hard distance constraints between circle centers.
• To validate the proposed method against existing techniques.

Main Methods:

• A physics-inspired simulation treating circle centers as moving objects with repulsive forces.
• Forces applied between circles and between circles and polygon boundaries, inversely proportional to distance.
• Adaptation of the method to incorporate hard upper/lower distance bounds.

Main Results:

• The proposed method efficiently handles non-convex polygons, a significant improvement over existing work.
• The algorithm produces near-optimal results quickly for various container shapes.
• The method successfully incorporates and respects distance constraints.

Conclusions:

• The developed method offers a practical and effective solution for the p-dispersion problem in complex geometries.
• This approach advances the field of facility placement and computational geometry.
• The technique provides a valuable tool for optimizing spatial arrangements with constraints.