Near-Linear Algorithms for Geometric Hitting Sets and Set Covers

被引：17

作者：

Agarwal, Pankaj K. ^{[1
]}

Pan, Jiangwei ^{[1
,2
]}

机构：

[1] Duke Univ, Dept Comp Sci, Box 90129, Durham, NC 27708 USA

[2] Netflix Inc, 100 Winchester Cir, Los Gatos, CA 95032 USA

来源：

DISCRETE & COMPUTATIONAL GEOMETRY | 2020年 / 63卷 / 02期

关键词：

Geometric set cover; Near-linear algorithms; Multiplicative weight method; Disks; Rectangles; EPSILON-NETS; APPROXIMATION ALGORITHMS; FRACTIONAL PACKING; BOUNDS; SIZE;

D O I：

10.1007/s00454-019-00099-6

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Given a finite range space Sigma = (X, R), with N = vertical bar X vertical bar+vertical bar R vertical bar, we present two simple algorithms, based on the multiplicative-weight method, for computing a small-size hitting set or set cover of Sigma. The first algorithm is a simpler variant of the BronnimannGoodrich algorithm but more efficient to implement, and the second algorithm can be viewed as solving a two-player zero-sum game. These algorithms, in conjunction with some standard geometric data structures, lead to near-linear algorithms for computing a small-size hitting set or set cover for a number of geometric range spaces. For example, they lead to O( Npolylog( N)) expected-time randomized O(1)-approximation algorithms for both hitting set and set cover if X is a set of points and R a set of disks in R-2.

引用

页码：460 / 482

页数：23