No, coreset, no cry

Sariel Har-Peled

doi:10.1007/978-3-540-30538-5_27

No, coreset, no cry

Sariel Har-Peled

Siebel School of Computing and Data Science

Research output: Contribution to journal › Article › peer-review

Abstract

We show that corrects do not exist for the problem of 2-slabs in ℝ³, thus demonstrating that the natural approach for solving approximately this problem efficiently is infeasible. On the positive side, for a point set P in ℝ³, 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.

Original language	English (US)
Pages (from-to)	324-335
Number of pages	12
Journal	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	3328
DOIs	https://doi.org/10.1007/978-3-540-30538-5_27
State	Published - 2004

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Online availability

10.1007/978-3-540-30538-5_27

Library availability

Discover UIUC Full Text

Cite this

@article{a92d3b61b686490dbe77f3ad5e7dff22,

title = "No, coreset, no cry",

abstract = "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.",

author = "Sariel Har-Peled",

note = "Funding Information: ★The full version of this paper is available from http://www.uiuc.edu/˜sariel/ papers/02/http://www.uiuc.edu/ sariel/papers/02/2slab/ 2slab/. ★★Work on this paper was partially supported by a NSF CAREER award CCR-0132901.",

year = "2004",

doi = "10.1007/978-3-540-30538-5_27",

language = "English (US)",

volume = "3328",

pages = "324--335",

journal = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

issn = "0302-9743",

publisher = "Springer",

}

TY - JOUR

T1 - No, coreset, no cry

AU - Har-Peled, Sariel

N1 - Funding Information: ★The full version of this paper is available from http://www.uiuc.edu/˜sariel/ papers/02/http://www.uiuc.edu/ sariel/papers/02/2slab/ 2slab/. ★★Work on this paper was partially supported by a NSF CAREER award CCR-0132901.

PY - 2004

Y1 - 2004

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=35048833881&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=35048833881&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-30538-5_27

DO - 10.1007/978-3-540-30538-5_27

M3 - Article

AN - SCOPUS:35048833881

SN - 0302-9743

VL - 3328

SP - 324

EP - 335

JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

ER -

No, coreset, no cry

Abstract

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this