Journal of South China University of Technology(Natural Science Edition) ›› 2019, Vol. 47 ›› Issue (12): 78-85.doi: 10.12141/j.issn.1000-565X.190370

• Architecture & Civil Engineering • Previous Articles     Next Articles

A Greedy Heuristic-based Approach to Solving the Discrete Unit Disk Cover Problem

Miao WANGSong-Tao WU2,Yong-Zhe LI3, 2   

  • Received:2019-06-23 Revised:2019-07-15 Online:2019-12-25 Published:2019-11-02
  • Contact: Miao WANG E-mail:wangmiao88414@163.com

Abstract: The current urban complex model proposed by the sharing economy has a limited service radius. The basic mathematical model for selecting the location of a complex is a discrete unit disk coverage (DUDC) problem. Given n points in a plane and unit disks with radius r, the objective of the DUDC problem is to determine a minimum number of the disks to cover all points. This paper presented an approach, which makes use of a greedy heuristic-based algorithm, to get the approximate optimal solution for the DUDC problem within polynomial time. The presented approach generated discrete cells to represent the 2D plane. Then, unit disks can be placed at the center of cells. Target points covered by the disks can be used to generate basic sets. A greedy algorithm was articulated to find a minimal combination of the covering sets that facilitates the realization of full coverage of all target points. The center of the minimal covering circles regarding the points in the sets was calculated and considered as the positions of the disks. Based on a case study, the effectiveness of the proposed algorithm has been validated. The factors that influence the performance of the algorithm were also discussed.

CLC Number: