We study the problem of minimizing the area of the convex hull of k polygons with a total of n vertices in the plane, under translations and rigid motions for any fixed k ≥ 3. For any ε ∈ (0, 1), we give (1 + ε)-approximation algorithms running in O(ε^{-1/2} log n + ε^{1/2 - k}) time for translations, and in O(ε^{-1/2} log n + ε^{3/2 - 2k}) time for rigid motions. We also consider minimizing the perimeter of the convex hull under translations and obtain a (1 + ε)-approximation algorithm running in O(ε^{-1/2} log n + ε^{1/2 - k}log^{k-1}(1/ε)) time. To the best of our knowledge, these are the first results of this kind for k ≥ 3 polygons. Furthermore, for the special case of two polygons with n₀ and n₁ vertices (n₀ ≥ n₁), respectively, we give an O(n₀+n₁log²(n₀+n₁))-time algorithm for the minimum-perimeter problem. This significantly improves upon the best-known O((n₀+n₁)log²(n₀+n₁)) bound by eliminating the logarithmic overhead associated with the larger input size n₀.

We study the problem of minimizing the convex hull of two convex polytopes with n vertices in total under translation in d-dimensional space ℝd for any fixed dimension d ≥ 2. For d ≥ 2, we present a deterministic O (n )-time algorithm returning a translation minimizing the area of the convex hull, improving upon the previously best O (n log n )-time algorithm. Our algorithm returns the smallest area of convex hulls under translation in the same time, and thus it is optimal. For d ≥ 3, we present a deterministic algorithm with running time O (n(d +1)/2) for odd d and O (nd /2 logd n ) for even d. This improves substantially upon the previously best algorithm by a factor at least n(d -1)/2 log n. We also consider the variant that two input polytopes are restricted to remain disjoint, and present a deterministic algorithm with running time O (nd+1) for odd d and O (nd logd -1 n) for even d. This improves substantially upon the previously best algorithm for d > 3 by factor nO (d2) We also study the problem of maximizing the overlap of two convex polytopes under translation in d-dimensional space ℝd for d ≥ 3. We give an -time algorithm, improving substantially upon the previously best algorithm by a factor at least n1-3/d logd +1 n.

The Hilbert metric, introduced by David Hilbert in 1895, is a projective metric defined on a bounded convex domain in a Euclidean space. For a convex polygon with m vertices and n point sites lying inside the polygon in the plane, it is shown that the nearest-point Voronoi diagram in the Hilbert metric has combinatorial complexity of O(mn) [Gezalyan and Mount, SoCG 2023]. In this paper, we show that the farthest-point Voronoi diagram in the Hilbert metric has combinatorial complexity O(m), which is independent of the number of sites. Also, we present an efficient algorithm to compute the farthest-point Voronoi diagram.