检索结果-内蒙古大学图书馆

On line-separable weighted unit-disk coverage and related problems

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2025年 129卷

作者： Liu, Gang Wang, Haitao Univ Utah Kahlert Sch Comp Salt Lake City UT 84112 USA

Given a set P of n points and a set S of n weighted disks in the plane, the disk coverage problem is to compute a subset of disks of smallest total weight such that the union of the disks in the subset covers all points of P. The problem is NP-hard. In this paper, we consider a line-separable unit-disk version of the problem where all disks have the same radius and their centers are separated from the points of P by a line & ell;. We present an O (n3/2 log2 n) time algorithm for the problem. This improves the previously best work of O (n2 log n) time. Our result leads to an algorithm of O (n7/2 log2 n) time for the halfplane coverage problem (i.e., using n weighted halfplanes to cover n points), an improvement over the previous O (n4 log n) time solution. If all halfplanes are lower ones, our algorithm runs in O (n3/2 log2 n) time, while the previous best algorithm takes O (n2 log n) time. Using duality, the hitting set problems under the same settings can be solved with similar time complexities. (c) 2025 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.

关键词： Line-separable Unit disks Halfplanes geometric coverage geometric hitting set

来源：评论

学校读者我要写书评

暂无评论

Algorithms for the Line-Constrained Disk coverage and Related Problems 17th

Algorithms for the Line-Constrained Disk Coverage and Relate...

引用

17th International Symposium on Algorithms and Data Structures (WADS)

作者： Pedersen, Logan Wang, Haitao Utah State Univ Dept Comp Sci Logan UT 84322 USA

ISBN: (纸本)9783030835088;9783030835071

Given a set P of n points and a set S of m weighted disks in the plane, the disk coverage problem asks for a subset of disks of minimum total weight that cover all points of P. The problem is NP-hard. In this paper, we consider a line-constrained version in which all disks are centered on a line L (while points of P can be anywhere in the plane). We present an O((m + n) log(m + n) +kappa log m) time algorithm for the problem, where kappa is the number of pairs of disks that intersect. For the unit-disk case where all disks have the same radius, the running time can be reduced to O((n + m) log(m + n)). In addition, we solve in O((m+ n) log(m+ n)) time the L-infinity and L-1 cases of the problem, in which the disks are squares and diamonds, respectively. Using our techniques, we further solve two other geometric coverage problems. Given in the plane a set P of n points and a set S of n weighted half-planes, we solve in O(n(4) log n) time the problem of finding a subset of half-planes to cover P so that their total weight is minimized. This improves the previous best algorithm of O(n(5)) time by almost a linear factor. If all half-planes are lower ones, our algorithm runs in O(n(2) log n) time, which improves the previous best algorithm of O(n(4)) time by almost a quadratic factor.

关键词： Disk coverage Line-constrained Half-plane coverage geometric coverage Facility location

来源：评论

学校读者我要写书评

暂无评论

Parameterized Complexity of geometric Covering Problems Having Conflicts

引用

ALGORITHMICA 2020年第1期82卷 1-19页

作者： Banik, Aritra Panolan, Fahad Raman, Venkatesh Sahlot, Vibha Saurabh, Saket Natl Inst Sci Educ & Res Bhubaneswar Odisha India Univ Bergen Dept Informat Bergen Norway HBNI Inst Math Sci Chennai Tamil Nadu India Indian Inst Technol Jodhpur Rajasthan India

The input for the geometric coverage problem consists of a pair sigma=(P,R), where P is a set of points in R-d and R is a set of subsets of P defined by the intersection of P with some geometric objects in R-d. Motivated by what are called choice problems in geometry, we consider a variation of the geometric coverage problem where there are conflicts on the covering objects that precludes some objects from being part of the solution if some others are in the solution. As our first contribution, we propose two natural models in which the conflict relations are given: (a) by a graph on the covering objects, and (b) by a representable matroid on the covering objects. Our main result is that as long as the conflict graph has bounded arboricity there is a parameterized reduction to the conflict-free version. As a consequence, we have the following results when the conflict graph has bounded arboricity. (1) If the geometric coverage problem is fixed parameter tractable (FPT), then so is the conflict free version. (2) If the geometric coverage problem admits a factor alpha-approximation, then the conflict free version admits a factor alpha-approximation algorithm running in FPT time. As a corollary to our main result we get a plethora of approximation algorithms that run in FPT time. Our other results include an FPT algorithm and a hardness result for conflict-free version of Covering Points by Intervals. The FPT algorithm is for the case when the conflicts are given by a representable matroid. We prove that conflict-free version of Covering Points by Intervals does not admit an FPT algorithm, unless FPT =W[1], for the family of conflict graphs for which the Independent Set problem is W[1]-hard.

关键词： Conflict problems geometric coverage Parameterized Complexity Matroids

来源：评论

学校读者我要写书评

暂无评论

Algorithms for covering multiple barriers

引用

THEORETICAL COMPUTER SCIENCE 2019年 758卷 61-72页

作者： Li, Shimin Wang, Haitao Utah State Univ Dept Comp Sci Logan UT 84322 USA

In this paper, we consider the problems for covering multiple intervals on a line. Given a set B of m line segments (called "barriers") on a horizontal line L and another set S of n horizontal line segments of the same length in the plane, we want to move all segments of S to L so that their union covers all barriers and the maximum movement of all segments of S is minimized. Previously, an O(n(3) log n)-time algorithm was given for the case m =1. In this paper, we propose an O(n(2) log n log log n+ nm log m)-time algorithm for a mare general setting with any m >= 1, which also improves the previous work when m =1. We then consider a line-constrained version of the problem in which the segments of S are all initially on the line I.. Previously, an O(n log n)-time algorithm was known for the case m = 1. We present an algorithm of O(m log m + n log m log n) time for any m >= 1. These problems may have applications in mobile sensor barrier coverage in wireless sensor networks. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Barrier coverage geometric coverage Mobile sensors Algorithms Data structures Computational geometry

来源：评论

学校读者我要写书评

暂无评论

Algorithms for the line-constrained disk coverage and related problems

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2022年第0期105-106卷

作者： Pedersen, Logan Wang, Haitao Utah State Univ Dept Comp Sci Logan UT 84322 USA

Given a set P of n points and a set S of m weighted disks in the plane, the disk coverage problem asks for a subset of disks of minimum total weight that cover all points of P. The problem is NP-hard. In this paper, we consider a line-constrained version in which all disks are centered on a line L (while points of P can be anywhere in the plane). We present an O ((m + n) log(m + n) + kappa log m) time algorithm for the problem, where kappa is the number of pairs of disks whose boundaries intersect. Alternatively, we can also solve the problem in O (nm log(m + n)) time. For the unit-disk case where all disks have the same radius, the running time can be reduced to O ((n + m) log(m + n)). In addition, we solve in O ((m + n) log(m + n)) time the L infinity and L1 cases of the problem, in which the disks are squares and diamonds, respectively. We further demonstrate that our techniques can also be used to solve other geometric coverage problems. For example, given in the plane a set P of n points and a set S of n weighted half-planes, we solve in O (n4 log n) time the problem of finding a subset of half-planes to cover P so that their total weight is minimized. This improves the previous best algorithm of O (n(5)) time by almost a linear factor. If all half-planes are lower ones, then our algorithm runs in O(n(2) log n) time, which improves the previous best algorithm of O (n(4)) time by almost a quadratic factor. (c) 2022 Elsevier B.V. All rights reserved.

关键词： Disk coverage Line-constrained Half-plane coverage geometric coverage

来源：评论

学校读者我要写书评

暂无评论

Algorithms for Covering Barrier Points by Mobile Sensors with Line Constraint

引用

International Journal of Computational Geometry and Applications 2024年第1n02期34卷 1-23页

作者： Jain, Princy Wang, Haitao Department of Computer Science Utah State University Logan UT United States Kahlert School of Computing University of Utah Salt Lake City UT United States

We study the problem of covering barrier points by mobile sensors. Each sensor is represented by a point in the plane with the same covering range >r so that any point within distance >r from the sensor can be covered by the sensor. Given a set >B of >m points (called "barrier points") and a set >S of >n points (representing the "sensors") in the plane, the problem is to move the sensors so that each barrier point is covered by at least one sensor and the maximum movement of all sensors is minimized. The problem is NP-hard. In this paper, we consider two line-constrained variations of the problem and present efficient algorithms that improve the previous work. In the first problem, all sensors are given on a line > and are required to move on > only while the barrier points can be anywhere in the plane. We propose an >O((n + m)log(n + m)) time algorithm for the problem. We also consider the weighted case where each sensor has a weight;we give an >O(mlog m + nlog2n) time algorithm for this case. In the second problem, all barrier points are on > while all sensors are in the plane but are required to move onto > to cover all barrier points. We also solve the weighted case in >O(mlog m + nlog2n) time. © 2024 World Scientific Publishing Company.

关键词： algorithms Barrier coverage barrier points computational geometry disk coverage geometric coverage line-constrained mobile sensors

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：