Convex Approximation by Spherical Patches

Kevin Buchin; Simon Plantinga; Günter Rote; Astrid Sturm; Gert Vegter

Convex Approximation by Spherical Patches

Kevin Buchin, Simon Plantinga, Günter Rote, Astrid Sturm, Gert Vegter

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic

123 Downloads (Pure)

Abstract

Given points in convex position in three dimensions, we want to find an approximating convex surface consisting of spherical patches, such that all points are within some specified tolerance bound ε of the approximating surface. We describe a greedy algorithm which constructs an approximating surface whose spherical patches are associated to the faces of an inscribed polytope. We show that deciding whether an approximation with not more than a given number of spherical patches exists is NP-hard.

Original language	English
Title of host publication	EPRINTS-BOOK-TITLE
Publisher	University of Groningen, Johann Bernoulli Institute for Mathematics and Computer Science
Number of pages	4
Publication status	Published - 2007

Access to Document

2007EurWCompGeomBuchin.pdfFinal publisher's version, 134 KB

Handle.net

Persistent link

Cite this

@inbook{ff361f9aa67f498fac13edf12db9da9d,

title = "Convex Approximation by Spherical Patches",

abstract = "Given points in convex position in three dimensions, we want to find an approximating convex surface consisting of spherical patches, such that all points are within some specified tolerance bound ε of the approximating surface. We describe a greedy algorithm which constructs an approximating surface whose spherical patches are associated to the faces of an inscribed polytope. We show that deciding whether an approximation with not more than a given number of spherical patches exists is NP-hard.",

author = "Kevin Buchin and Simon Plantinga and G{\"u}nter Rote and Astrid Sturm and Gert Vegter",

note = "Relation: http://www.rug.nl/informatica/organisatie/overorganisatie/iwi Rights: University of Groningen. Research Institute for Mathematics and Computing Science (IWI)",

year = "2007",

language = "English",

booktitle = "EPRINTS-BOOK-TITLE",

publisher = "University of Groningen, Johann Bernoulli Institute for Mathematics and Computer Science",

}

TY - CHAP

T1 - Convex Approximation by Spherical Patches

AU - Buchin, Kevin

AU - Plantinga, Simon

AU - Rote, Günter

AU - Sturm, Astrid

AU - Vegter, Gert

N1 - Relation: http://www.rug.nl/informatica/organisatie/overorganisatie/iwi Rights: University of Groningen. Research Institute for Mathematics and Computing Science (IWI)

PY - 2007

Y1 - 2007

N2 - Given points in convex position in three dimensions, we want to find an approximating convex surface consisting of spherical patches, such that all points are within some specified tolerance bound ε of the approximating surface. We describe a greedy algorithm which constructs an approximating surface whose spherical patches are associated to the faces of an inscribed polytope. We show that deciding whether an approximation with not more than a given number of spherical patches exists is NP-hard.

AB - Given points in convex position in three dimensions, we want to find an approximating convex surface consisting of spherical patches, such that all points are within some specified tolerance bound ε of the approximating surface. We describe a greedy algorithm which constructs an approximating surface whose spherical patches are associated to the faces of an inscribed polytope. We show that deciding whether an approximation with not more than a given number of spherical patches exists is NP-hard.

M3 - Chapter

BT - EPRINTS-BOOK-TITLE

PB - University of Groningen, Johann Bernoulli Institute for Mathematics and Computer Science

ER -

Convex Approximation by Spherical Patches

Abstract

Access to Document

Handle.net

Fingerprint

Cite this