EconPapers    
Economics at your fingertips  
 

Repulsion-based p-dispersion with distance constraints in non-convex polygons

Zhengguan Dai (), Kathleen Xu () and Melkior Ornik ()
Additional contact information
Zhengguan Dai: University of Illinois Urbana-Champaign
Kathleen Xu: University of Illinois Urbana-Champaign
Melkior Ornik: University of Illinois Urbana-Champaign

Annals of Operations Research, 2021, vol. 307, issue 1, No 5, 75-91

Abstract: Abstract Motivated by the question of optimal facility placement, the classical p-dispersion problem seeks to place a fixed number of equally sized non-overlapping circles of maximal possible radius into a subset of the plane. While exact solutions to this problem may be found for placement into particular sets, the problem is provably NP-complete for general sets, and existing work is largely restricted to geometrically simple sets. This paper makes two contributions to the theory of p-dispersion. First, we propose a computationally feasible suboptimal approach to the p-dispersion problem for all non-convex polygons. The proposed method, motivated by the mechanics of the p-body problem, considers circle centers as continuously moving objects in the plane and assigns repulsive forces between different circles, as well as circles and polygon boundaries, with magnitudes inversely proportional to the corresponding distances. Additionally, following the motivating application of optimal facility placement, we consider existence of additional hard upper or lower distance bounds on pairs of circle centers, and adapt the proposed method to provide a p-dispersion solution that provably respects such constraints. We validate our proposed method by comparing it with previous exact and approximate methods for p-dispersion. The method quickly produces near-optimal results for a number of containers.

Keywords: Dispersion; Packing; Location; Strategic planning (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10479-021-04281-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:307:y:2021:i:1:d:10.1007_s10479-021-04281-z

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-021-04281-z

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().

 
Page updated 2025-03-20
Handle: RePEc:spr:annopr:v:307:y:2021:i:1:d:10.1007_s10479-021-04281-z