Scholarlink

<p>In this study, we investigate the unit disk cover (UDC) problem, which is one of the important NP-hard problems, playing a vital role in applications such as wireless communication, sensor networks, and resource allocation. As the demand for efficient network design grows in an increasingly connected world, it becomes paramount to find effective solutions to the UDC problem, particularly when dealing with large-scale datasets and real-time constraints. To address these complexities, we present two novel heuristic algorithms that utilize Voronoi diagrams, a powerful geometric tool, and are specifically designed to take advantage of high-performance computing (HPC) capabilities. Both algorithms have a running time of <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(O(n \log n)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, and their output results provide better results compared to previous algorithms, enabling them to process large datasets efficiently and deliver results in real-time scenarios. We validate our approaches through extensive experiments on various randomly generated datasets with different distributions, comparing our findings with significant prior algorithms. Our analysis demonstrates that both algorithms perform desirably, particularly the second algorithm, which provides the best solution over 90 percent of the time in comparison to other methods. These enhancements not only showcase the feasibility of applying HPC resources, but also highlight the practical relevance of our algorithms in real-world applications where quick decision-making is critical.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Voronoi-based heuristic strategies for efficient solutions to the unit disk cover problem

  • 期刊论文

  • 发表日期：

    2026年4月24日

查看全文
  • Mahdi Imanparast

摘要

In this study, we investigate the unit disk cover (UDC) problem, which is one of the important NP-hard problems, playing a vital role in applications such as wireless communication, sensor networks, and resource allocation. As the demand for efficient network design grows in an increasingly connected world, it becomes paramount to find effective solutions to the UDC problem, particularly when dealing with large-scale datasets and real-time constraints. To address these complexities, we present two novel heuristic algorithms that utilize Voronoi diagrams, a powerful geometric tool, and are specifically designed to take advantage of high-performance computing (HPC) capabilities. Both algorithms have a running time of \(O(n \log n)\) O ( n log n ) , and their output results provide better results compared to previous algorithms, enabling them to process large datasets efficiently and deliver results in real-time scenarios. We validate our approaches through extensive experiments on various randomly generated datasets with different distributions, comparing our findings with significant prior algorithms. Our analysis demonstrates that both algorithms perform desirably, particularly the second algorithm, which provides the best solution over 90 percent of the time in comparison to other methods. These enhancements not only showcase the feasibility of applying HPC resources, but also highlight the practical relevance of our algorithms in real-world applications where quick decision-making is critical.