Improved results on geometric hitting set problems

Nabil H. Mustafa, Saurabh Ray

Research output: Contribution to journalArticlepeer-review

Abstract

We consider the problem of computing minimum geometric hitting sets in which, given a set of geometric objects and a set of points, the goal is to compute the smallest subset of points that hit all geometric objects. The problem is known to be strongly NP-hard even for simple geometric objects like unit disks in the plane. Therefore, unless P = NP, it is not possible to get Fully Polynomial Time Approximation Algorithms (FPTAS) for such problems. We give the first PTAS for this problem when the geometric objects are half-spaces in ℝ3 and when they are an r-admissible set regions in the plane (this includes pseudo-disks as they are 2-admissible). Quite surprisingly, our algorithm is a very simple local-search algorithm which iterates over local improvements only.

Original languageEnglish (US)
Pages (from-to)883-895
Number of pages13
JournalDiscrete and Computational Geometry
Volume44
Issue number4
DOIs
StatePublished - 2010

Keywords

  • Approximation algorithms
  • Epsilon nets
  • Greedy algorithms
  • Hitting sets
  • Local search
  • Transversals

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Improved results on geometric hitting set problems'. Together they form a unique fingerprint.

Cite this