2026-07-30T20:32:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17405 2024-03-06T10:59:40Z ddc:004 open_access

Inscribing or Circumscribing a Histogon to a Convex Polygon Chung, Jaehoon Bae, Sang Won Shin, Chan-Su Yoon, Sang Duk Ahn, Hee-Kap Shape simplification Shape analysis Histogon Convex polygon We consider two optimization problems of approximating a convex polygon, one by a largest inscribed histogon and the other by a smallest circumscribed histogon. An axis-aligned histogon is an axis-aligned rectilinear polygon such that every horizontal edge has an integer length. A histogon of orientation θ is a copy of an axis-aligned histogon rotated by θ in counterclockwise direction. The goal is to find a largest inscribed histogon and a smallest circumscribed histogon over all orientations in [0,π). Depending on whether the horizontal width of a histogon is predetermined or not, we consider several different versions of the problem and present exact algorithms. These optimization problems belong to shape analysis, classification, and simplification, and they have applications in various cost-optimization problems. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jaehoon Chung and Sang Won Bae and Chan-Su Shin and Sang Duk Yoon and Hee-Kap Ahn 2022 Is Part Of LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2022.13 urn:nbn:de:0030-drops-174054 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.13 eng https://creativecommons.org/licenses/by/4.0/legalcode