Minkowski Sum Construction and other Applications of Arrangements: and the Importance of Being Exact - Couverture souple

Fogel, Efraim

 
9783843380942: Minkowski Sum Construction and other Applications of Arrangements: and the Importance of Being Exact
Couverture souple
ISBN 10 : 3843380945 ISBN 13 : 9783843380942
Editeur : LAP LAMBERT Academic Publishing, 2010

Synopsis

We present two exact implementations of efficient output-sensitive algorithms that compute Minkowski sums of two convex polytopes in three-dimensional space. We do not assume general position. Namely, we handle degenerate input and produce exact results. We provide a tight bound on the exact maximum complexity of Minkowski sums of convex polytopes in the space in terms of the number of facets of the summands. The complexity of Minkowski sum structures is directly related to the time consumption of our Minkowski sum constructions, as they are output sensitive. The algorithms employ a data structure that represents arrangements embedded on two-dimensional parametric surfaces in the space and make use of many operations applied to arrangements. We also present an exact implementations an efficient algorithm that partitions an assembly of polytopes in the space with two hands using infinite translations. This application makes extensive use of Minkowski-sum constructions and other operations on arrangements of geodesic arcs embedded on the sphere. It distinctly shows the importance of exact computation, as imprecise computation might result with dismissal of valid partitioning-motions.

Les informations fournies dans la section « Synopsis » peuvent faire référence à une autre édition de ce titre.

Présentation de l'éditeur

We present two exact implementations of efficient output-sensitive algorithms that compute Minkowski sums of two convex polytopes in three-dimensional space. We do not assume general position. Namely, we handle degenerate input and produce exact results. We provide a tight bound on the exact maximum complexity of Minkowski sums of convex polytopes in the space in terms of the number of facets of the summands. The complexity of Minkowski sum structures is directly related to the time consumption of our Minkowski sum constructions, as they are output sensitive. The algorithms employ a data structure that represents arrangements embedded on two-dimensional parametric surfaces in the space and make use of many operations applied to arrangements. We also present an exact implementations an efficient algorithm that partitions an assembly of polytopes in the space with two hands using infinite translations. This application makes extensive use of Minkowski-sum constructions and other operations on arrangements of geodesic arcs embedded on the sphere. It distinctly shows the importance of exact computation, as imprecise computation might result with dismissal of valid partitioning-motions.

Biographie de l'auteur

Dr. Efraim Fogel (Efi) is a researcher in the Blavatnik school of computer science at the Tel Aviv university, Israel, and a consultant in the fields of Computational Geometry and 3D Graphics. Efi received a Ph.D. degree from the Tel Aviv university. He received an M.Sc. degree from the Stanford university, California, USA.

Les informations fournies dans la section « A propos du livre » peuvent faire référence à une autre édition de ce titre.

Éditeur
LAP LAMBERT Academic Publishing
Date d'édition
2010
Langue
anglais
ISBN 10 
3843380945
ISBN 13 
9783843380942
Reliure
Broché
Nombre de pages
144
Coordonnées du fabricant
non disponible
Personne responsable
KreGa Onlinehandel GmbH
4950000000000
info@krega-onlinehandel.de

Birkenweg 31
Brakel
33034
Allemagne