基于贪心算法的离散单位圆盘覆盖问题研究

Journal article (2019)

Authors

Miao Wang Harbin Institute of Technology
Songtao Wu Harbin Institute of Technology
Yue Wu Harbin Institute of Technology
Research Group
Pattern Recognition and Bioinformatics (EEMCS) (TU Delft)
More Info
expand_more

Published Date

2019

Language

Chinese

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Intelligent Systems

Research Group

Pattern Recognition and Bioinformatics

Abstract

A greedy heuristic-based algorithm was put forward to obtain the approximate optimal solution for the DUDC(discrete unit disk cover) problem within polynomial time. Firstly, discrete cells were generated to represent the 2D plane. Then, alternative sets which can cover certain amount of target points were built. A greedy algorithm was articulated to find a minimal combination of the alternative sets, and full coverage of all target points was realized. The minimal covering circles were calculated considering the position of each point in the sets. The center of the minimal covering circles was selected as the location. Based on a case study, the effectiveness of the proposed algorithm was validated. The factors of influence the performance of the algorithm were also discussed and ratio of time complexity and approximation was analyzed.

Files

_.pdf
(pdf | 3.54 Mb)

Download not available