Experiments with unit disk cover algorithms for covering massive pointsets
Experiments with unit disk cover algorithms for covering massive pointsets
复制标题
用于覆盖海量点集的单位圆盘覆盖算法的实验
DOI：
10.1016/j.comgeo.2022.101925
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Shevchenko, Ronald
中科院分区：
文献类型：
--
作者：
Friederich, Rachel;Ghosh, Anirban;Graham, Matthew;Hicks, Brian;Shevchenko, Ronald
给定平面上的一组n个点，单位圆盘覆盖（UDC）问题要求计算覆盖这些点所需的最小单位圆盘数，沿着圆盘的放置。这个问题是NP-难的，在过去的三十年里已经设计了几个近似算法。在本文中，我们已经设计和实验比较了这些算法在大量点集上的实际性能。我们的目标是调查哪些算法运行速度快，并在实践中给出良好的近似。我们提出了一个简单的UDC的7-近似算法，该算法在O（n）的预期时间内运行，并使用O（s）的额外空间，其中s表示生成的覆盖的大小。在我们的实验中，它被证明是最快的。我们还提出了两种方法来减少它生成的封面的大小，而不会减慢它。据我们所知，这是第一项通过实验比较UDC问题算法的工作。使用大规模点集（数百万）进行的实验揭示了它们的实际用途。我们通过GitHub 1共享工程算法，以在几何优化领域进行更广泛的使用和未来的研究。
Given a set of n points in the plane, the Unit Disk Cover (UDC) problem asks to compute the minimum number of unit disks required to cover the points, along with a placement of the disks. The problem is NP-hard and several approximation algorithms have been designed over the last three decades. In this paper, we have engineered and experimentally compared practical performances of some of these algorithms on massive pointsets. The goal is to investigate which algorithms run fast and give good approximation in practice. We present a simple 7-approximation algorithm for UDC that runs in O (n) expected time and uses O (s) extra space, where s denotes the size of the generated cover. In our experiments, it turned out to be the speediest of all. We also present two heuristics to reduce the sizes of covers generated by it without slowing it down by much. To our knowledge, this is the first work that experimentally compares algorithms for the UDC problem. Experiments with them using massive pointsets (in the order of millions) throw light on their practical uses. We share the engineered algorithms via GitHub 1 for broader uses and future research in the domain of geometric optimization.