Publications

Home Activities Publications

Abstract: We consider two optimization problems of approximating a convex polygon in the plane, 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 theta is a copy of an axis-aligned histogon rotated by theta in a counterclockwise direction. Our goal is to compute a largest inscribed histogon and a smallest circumscribed histogon over all orientations in [0, pi). 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 for these versions of the inscribed histogon problem. For the circumscribed histogon problem, we present an efficient algorithm whose running time depends on the diameter and the number of vertices of the input polygon. These optimization problems belong to shape analysis, classification, and simplification, and they have applications in various cost-optimization problems. (c) 2025 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.

List