Opening book details…
Can I read Implementation and Parallelization of a Reverse-Search Algorithm for Minkowski Sums on EtoBox?
Implementation and Parallelization of a Reverse-Search Algorithm for Minkowski Sums by Christophe Weibel is a book available to read on EtoBox.
What is Implementation and Parallelization of a Reverse-Search Algorithm for Minkowski Sums about?
We present an implementation of a reverse-search algorithm of Fukuda for computing Minkowski sums of polytopes efficiently. The algorithm allows summing any number of polytopes in any dimension, and is complete in the sense that it does not assume general position. Its running time depends linearly on the size of the output. To the best of our knowledge, this is the only existing implementation that can efficiently compute Minkowski sums in higher dimensions. The implementation uses the exact arithmetic GMP, which ensures robustness of the program and exactness of the results. We furthermore present a parallel version of our implementation to demonstrate the simplicity and efficiency of performing the reverse search in parallel. The results of the performance tests show a near-linear acceleration of our parallel implementation.
- Author
- Christophe Weibel
- Publisher
- Society for Industrial and Applied Mathematics (SIAM, 3600 Market Street, Floor 6, Philadelphia, PA 19104)
- Published
- 2010
- Language
- EN
- ISBN
- 9780898719314
More by Christophe Weibel
Browse all works by Christophe Weibel
Similar books
- Search Engine Algorithm and Search Engine Marketing — Subhankar Das (2021)
- A Parallelization of Dijkstra's Shortest Path Algorithm — A. Crauser; K. Mehlhorn; U. Meyer; P. Sanders (1998)
- Software and Hardware Cooperative Implementation of the Rafflesia Optimization Algorithm — Zonglin Fu; Jeng-Shyang Pan; Yundong Guo; Václav Snášel (2023)
- An Adaptive Optimization Strict Reverse Navigation Algorithm for Ship Fine Alignment Process — Junwei Wang; Xiyuan Chen; Xin Shao; Zhen Ma (2021)
- A Fast Minimum Degree Algorithm and Matching Lower Bound — Robert Cummings; Matthew Fahrbach; Animesh Fatehpuria (2021)
- A Parallel Algorithm Synthesis Procedure for High-Performance Computer Architectures (Series in Computer Science) — Ian N. Dunn and Gerard G.L. Meyer (2012)