Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 0930.68152
Milenkovic, Victor J.
Rotational polygon containment and minimum enclosure using only robust 2D constructions. (English)
[J] Comput. Geom. 13, No.1, 3-19 (1999). ISSN 0925-7721

Summary: An algorithm and a robust floating point implementation is given for rotational polygon containment: given polygons $P_1,P_2,P_3,\dots, P_k$ and a container polygon $C$, find rotations and translations for the $k$ polygons that place them into the container without overlapping. A version of the algorithm and implementation also solves rotational minimum enclosure: given a class ${\cal C}$ of container polygons, find a container $C\in{\cal C}$ of minimum area for which containment has a solution. The minimum enclosure is approximate: it bounds the minimum area between $(1-\varepsilon)A$ and $A$. Experiments indicate that finding the minimum enclosure is practical for $k= 2,3$ but not larger unless optimality is sacrificed or angles ranges are limited (although these solutions can still be useful). Important applications for these algorithm to industrial problems are discussed. The paper also gives practical algorithms and numerical techniques for robustly calculating polygon set intersection, Minkowski sum, and range intersection: the intersection of a polygon with itself as it rotates through a range of angles. In particular, it introduces nearest pair rounding, which allows all these calculations to be carried out in rounded floating point arithmetic.

MSC 2000:: *68U05 Computational geometry, etc.

Keywords: rotational polygon containment

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]