No, coreset, no cry

Research output: Contribution to journalArticlepeer-review


We show that corrects do not exist for the problem of 2-slabs in ℝ3, thus demonstrating that the natural approach for solving approximately this problem efficiently is infeasible. On the positive side, for a point set P in ℝ3, we describe a near linear time algorithm for computing a (1 + ε)-approximation to the minimum width 2-slab cover of P. This is a first step in providing an efficient approximation algorithm for the problem of covering a point set with k-slabs.

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'No, coreset, no cry'. Together they form a unique fingerprint.

Cite this