On the Minimum-Area Parallelogram Annulus Problem

Abstract

The minimum-area parallelogram annulus problem is studied, in which one wants to compute a parallelogram annulus of minimum area that includes n input points in the plane. Extending an usual, doughnut-shaped circular annulus, a parallelogram annulus is defined to be a region between two edge-parallel parallelograms. As a parallelogram has two distinct orientations for its sides, so does a parallelogram annulus as well. In this paper, several variants of the problem are considered: (1) when both side orientations are given and fixed, (2) when one of them is fixed and the other can be freely chosen, (3) when the interior angles of the resulting parallelogram annulus is given and fixed, and (4) when both side orientations can be chosen arbitrarily. The first and efficient algorithms for each of these cases are presented, whose running times are (1) O(n), (2) O(n2logn), (3) O(n2logn), and (4) O(n4+ϵ), respectively. Further, bicriteria variants of the problem are considered, in which both width and area of the resulting parallelogram annulus are simultaneously minimized. In order to obtain these new algorithms, geometric observations, newly obtained in this paper and known in previous papers, and the symmetric nature of parallelograms and parallelogram annuli are exploited.

Keywords

• computational geometry
• geometric location
• geometric optimization
• parallelogram
• parallelogram annulus
• area