JCSE, vol. 15, no. 2, pp.78-83, 2021

DOI: http://dx.doi.org/10.5626/JCSE.2021.15.2.78

Minimum-Width Parallelogram Annulus with Given Angles

Sang Won Bae
Division of Artificial Intelligence and Computer Engineering, Kyonggi University, Suwon, Korea

Abstract: In this paper, we study a variant of the problem of computing a minimum-width parallelogram annulus that encloses a given set of n points in the plane. A parallelogram annulus is a closed region between a parallelogram and its inward offset. Specifically, we present the first algorithm that computes a minimum-width parallelogram annulus with inner angles fixed by the input that encloses n input points. The running time is O(n2 log n). To the best of our knowledge, there exists no known algorithm in the literature for the stated problem, and our algorithm generalizes the existing O(n2 log n)-time algorithm for the rectangular annulus in arbitrary orientation in the same running time-bound.

Keyword: Algorithms design and analysis; Computational geometry; Parallelogram annulus; Arbitrary orientation

Full Paper:   109 Downloads, 889 View