An Efficient Algorithm to Calculate the Minkowski Sum of Convex 3D Polyhedra

Henk Bekker; Jos B.T.M. Roerdink

An Efficient Algorithm to Calculate the Minkowski Sum of Convex 3D Polyhedra

Henk Bekker, Jos B.T.M. Roerdink

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

20 Citations (Scopus)

281 Downloads (Pure)

Abstract

A new method is presented to calculate the Minkowski sum of two convex polyhedra A and B in 3D. These graphs are given edge attributes. From these attributed graphs the attributed graph of the Minkowski sum is constructed. This graph is then transformed into the Minkowski sum of A and B. The running time of the algorithm is linear in the number of edges of the Minkowski sum.

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	10
Publication status	Published - 2001

Access to Document

2001LNCSBekker.pdfFinal publisher's version, 432 KB

Handle.net

Persistent link

Cite this

@inbook{5aac9bca5c8d421794e8181fb0b0d62c,

title = "An Efficient Algorithm to Calculate the Minkowski Sum of Convex 3D Polyhedra",

abstract = "A new method is presented to calculate the Minkowski sum of two convex polyhedra A and B in 3D. These graphs are given edge attributes. From these attributed graphs the attributed graph of the Minkowski sum is constructed. This graph is then transformed into the Minkowski sum of A and B. The running time of the algorithm is linear in the number of edges of the Minkowski sum.",

author = "Henk Bekker and Roerdink, {Jos B.T.M.}",

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

year = "2001",

language = "English",

booktitle = "EPRINTS-BOOK-TITLE",

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

}

TY - CHAP

T1 - An Efficient Algorithm to Calculate the Minkowski Sum of Convex 3D Polyhedra

AU - Bekker, Henk

AU - Roerdink, Jos B.T.M.

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

PY - 2001

Y1 - 2001

N2 - A new method is presented to calculate the Minkowski sum of two convex polyhedra A and B in 3D. These graphs are given edge attributes. From these attributed graphs the attributed graph of the Minkowski sum is constructed. This graph is then transformed into the Minkowski sum of A and B. The running time of the algorithm is linear in the number of edges of the Minkowski sum.

AB - A new method is presented to calculate the Minkowski sum of two convex polyhedra A and B in 3D. These graphs are given edge attributes. From these attributed graphs the attributed graph of the Minkowski sum is constructed. This graph is then transformed into the Minkowski sum of A and B. The running time of the algorithm is linear in the number of edges of the Minkowski sum.

M3 - Chapter

BT - EPRINTS-BOOK-TITLE

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

ER -

An Efficient Algorithm to Calculate the Minkowski Sum of Convex 3D Polyhedra

Abstract

Access to Document

Handle.net

Fingerprint

Cite this