TY - GEN
T1 - A new algorithm for the computation of the Minkowski difference of convex polyhedra
AU - Barki, Hichem
AU - Denis, Florence
AU - Dupont, Florent
PY - 2010
Y1 - 2010
N2 - We present a new algorithm, based on the concept of contributing vertices, for the exact and efficient computation of the Minkowski difference of convex polyhedra. First, we extend the concept of contributing vertices for the Minkowski difference case. Then, we generate a Minkowski difference facets superset by exploiting the information provided by the computed contributing vertices. Finally, we compute the Minkowski difference polyhedron through the trimming of the generated superset. We compared our Contributing Vertices-based Minkowski Difference (CVMD) algorithm to a Nef polyhedra-based approach using Minkowski addition, complement, transposition, and union operations. The performance benchmark shows that our CVMD algorithm outperforms the indirect Nef polyhedrabased approach. All our implementations use exact number types, produce exact results, and are based on CGAL, the Computational Geometry Algorithms Library.
AB - We present a new algorithm, based on the concept of contributing vertices, for the exact and efficient computation of the Minkowski difference of convex polyhedra. First, we extend the concept of contributing vertices for the Minkowski difference case. Then, we generate a Minkowski difference facets superset by exploiting the information provided by the computed contributing vertices. Finally, we compute the Minkowski difference polyhedron through the trimming of the generated superset. We compared our Contributing Vertices-based Minkowski Difference (CVMD) algorithm to a Nef polyhedra-based approach using Minkowski addition, complement, transposition, and union operations. The performance benchmark shows that our CVMD algorithm outperforms the indirect Nef polyhedrabased approach. All our implementations use exact number types, produce exact results, and are based on CGAL, the Computational Geometry Algorithms Library.
KW - Contributing vertices
KW - Minkowski difference
KW - Minkowski sum
KW - Nef polyhedra
UR - http://www.scopus.com/inward/record.url?scp=77956426131&partnerID=8YFLogxK
U2 - 10.1109/SMI.2010.12
DO - 10.1109/SMI.2010.12
M3 - Conference contribution
AN - SCOPUS:77956426131
SN - 9780769540726
T3 - SMI 2010 - International Conference on Shape Modeling and Applications, Proceedings
SP - 206
EP - 210
BT - SMI 2010 - International Conference on Shape Modeling and Applications, Proceedings
PB - IEEE Computer Society
T2 - International Conference on Shape Modeling and Applications - Shape Modeling International Conference, SMI 2010
Y2 - 21 June 2010 through 23 June 2010
ER -