|
Construction of the minimal enclosing parallelogram
A. D. Vainshtein
Abstract:
We consider the problem of constructing a minimal-area parallelogram that contains a given $n$-point set $N$. We give a characterization of locally extremal parallelograms; in the nondegenerate case their number is equal to the number of sides of the convex hull of $N$. This makes it possible to give an algorithm for solving the problem with complexity $O(n\log n)$. We also consider the situation when the convex hull $N$ is known a priori. We indicate a method for transfer from one local extremum to another that makes it possible to lower the estimate of the complexity to $O(n)$.
Received: 28.09.1989
Citation:
A. D. Vainshtein, “Construction of the minimal enclosing parallelogram”, Diskr. Mat., 2:4 (1990), 72–81
Linking options:
https://www.mathnet.ru/eng/dm886 https://www.mathnet.ru/eng/dm/v2/i4/p72
|
Statistics & downloads: |
Abstract page: | 520 | Full-text PDF : | 170 | First page: | 1 |
|