English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We present two exact implementations of efficient output-sensitive algorithmsthat compute Minkowski sums of two convex polyhedra in 3D. We do not assumegeneral position. Namely, we handle degenerate input, and produce exactresults. We provide a tight bound on the exact maximum complexity of Minkowskisums of polytopes in 3D in terms of the number of facets of the summandpolytopes. The algorithms employ variants of a data structure that representsarrangements embedded on two-dimensional parametric surfaces in 3D, and theymake use of many operations applied to arrangements in these representations.We have developed software components that support the arrangementdata-structure variants and the operations applied to them. These softwarecomponents are generic, as they can be instantiated with any number type.However, our algorithms require only (exact) rational arithmetic. Thesesoftware components together with exact rational-arithmetic enable a robust,efficient, and elegant implementation of the Minkowski-sum constructions andthe related applications. These software components are provided through apackage of the Computational Geometry Algorithm Library (CGAL) calledArrangement_on_surface_2. We also present exact implementations of otherapplications that exploit arrangements of arcs of great circles embedded on thesphere. We use them as basic blocks in an exact implementation of an efficientalgorithm that partitions an assembly of polyhedra in 3D with two hands usinginfinite translations. This application distinctly shows the importance ofexact computation, as imprecise computation might result with dismissal ofvalid partitioning-motions.

Minkowski Sum Construction and other Applications of Arrangements of Geodesic Arcs on the Sphere