Practical and efficient algorithms for the geometric hitting set problem

Norbert Bus, Nabil H. Mustafa, Saurabh Ray

Research output: Contribution to journalArticle

Abstract

The geometric hitting set problem is one of the basic geometric combinatorial optimization problems: given a set P of points and a set D of geometric objects in the plane, the goal is to compute a small-sized subset of P that hits all objects in D. Recently Agarwal and Pan (2014) presented a near-linear time algorithm for the case where D consists of disks in the plane. The algorithm uses sophisticated geometric tools and data structures with large resulting constants. In this paper, we design a hitting-set algorithm for this case without the use of these data-structures, and present experimental evidence that our new algorithm has near-linear running time in practice, and computes hitting sets within 1.3-factor of the optimal hitting set. We further present dnet, a public source-code module that incorporates this improvement, enabling fast and efficient computation of small-sized hitting sets in practice.

Original languageEnglish (US)
Pages (from-to)25-32
Number of pages8
JournalDiscrete Applied Mathematics
Volume240
DOIs
StatePublished - May 11 2018

Keywords

  • Approximation algorithms
  • Computational geometry
  • Geometric hitting sets

ASJC Scopus subject areas

  • Applied Mathematics
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Practical and efficient algorithms for the geometric hitting set problem'. Together they form a unique fingerprint.

  • Cite this