|
| << previous | next >> |
Journal description
All volumes of the corresponding journal
All issues of the corresponding volume
All articles of the corresponding issues
Details for article 6 of 12 found articles
| Title: |
Determining in Linear Time the Minimum Area Convex Hull of Two Polygons |
| Author: |
Lee, Hyun-Chan Woo, Tony C. |
| Appeared in: |
IIE transactions |
| Paging: | Volume 20 (1988) nr. 4 pages 338-345 |
| Year: |
1988-12-01 |
| Contents: |
As preprocessing for the two-dimensional cutting stock problem or pallet loading problem, we compute the minimum area convex hull. Given two polygons P and Q, we find their relative positions such that the convex hull encasing them is minimum in area. Let N be the total number of vertices in P and Q. We determine the minimum area convex hull in O(N) time. Q is allowed to translate by any amount relative to P, while assuming a constant number of orientations. Instead of recomputing the convex hull after every translation, we update the computed area at certain critical points. Linearity follows by showing that there are O(N) such critical points. |
| Publisher: |
Taylor & Francis |
| Source file: |
Elektronische Wetenschappelijke Tijdschriften |
Details for article 6 of 12 found articles
| << previous | next >> |