2026-08-25T17:34:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27180 2026-08-25T13:18:16Z ddc:004 open_access

Smallest Convex Hulls of Polygons Jung, Mook Kwon Ahn, Hee-Kap Convex hull packing bundling approximation algorithms cuttings 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₀. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mook Kwon Jung and Hee-Kap Ahn 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.44 urn:nbn:de:0030-drops-271803 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.44 eng https://creativecommons.org/licenses/by/4.0/legalcode