Scandinavian thins on top of cake: new and improved algorithms for stacking and packing

DOI10.1007/S00224-013-9493-9MaRDI QIDQ489760zbMATH OpenOpenAlexFDO

Authors Helmut Alt, Esther M. Arkin, Alon Efrat, Ferran Hurtado, Irina Kostitsyna, Alexander Kröller, Joseph S. B. Mitchell, Valentin Polishchuk, George W. Hart

Publication date 21 January 2015

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-013-9493-9

zbMATH Keywords

computational geometryenclosurepacking

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Recommendations

• scientific article; zbMATH DE number 1786500
• Approximating minimum-area rectangular and convex containers for packing convex polygons
• scientific article; zbMATH DE number 6698326
• Enclosing a Set of Objects by Two Minimum Area Rectangles
• Optimal rectangle packing

Cites work

• A polynomial solution for the Potato-peeling problem
• Algorithms and Computation
• Aligning two convex figures to minimize area or perimeter
• Approximating extent measures of points.
• Approximating largest convex hulls for imprecise points
• Computational geometry. Algorithms and applications.
• Computing and Combinatorics
• Computing closely matching upper and lower bounds on textile nesting problems
• Computing the maximum overlap of two convex polygons under translations
• Dense packings of congruent circles in a circle
• Determining the minimum-area encasing rectangle for an arbitrary closed curve
• Disk packing for the estimation of the size of a wire bundle
• Enclosing a Set of Objects by Two Minimum Area Rectangles
• Faster core-set constructions and data-stream algorithms in fixed dimensions
• Finding Extremal Polygons
• Finding minimal enclosing boxes
• Finding the upper envelope of n line segments in O(n log n) time
• Geometric Knapsack problems
• scientific article; zbMATH DE number 4180839 (Why is no real title available?)
• scientific article; zbMATH DE number 177850 (Why is no real title available?)
• scientific article; zbMATH DE number 1256725 (Why is no real title available?)
• scientific article; zbMATH DE number 1979490 (Why is no real title available?)
• scientific article; zbMATH DE number 1786500 (Why is no real title available?)
• scientific article; zbMATH DE number 1424289 (Why is no real title available?)
• Largest bounding box, smallest diameter, and related problems on imprecise points
• Matching convex shapes with respect to the symmetric difference
• Maximizing the area of overlap of two unions of disks under rigid motion
• Maximizing the overlap of two planar convex sets under rigid motions
• Maximum overlap and minimum convex hull of two convex polyhedra under translations
• Maximum overlap of convex polytopes under translation
• Minimum-perimeter enclosures
• More optimal packings of equal circles in a square
• Multiple translational containment. I: An approximate algorithm
• ON COMPUTING ENCLOSING ISOSCELES TRIANGLES AND RELATED PROBLEMS
• On the minimum perimeter triangle enclosing a convex polygon
• On the Minimum Volume Covering Ellipsoid of Ellipsoids
• Packing a cake into a box
• POLYGON CONTAINMENT AND TRANSLATIONAL IN-HAUSDORFF-DISTANCE BETWEEN SEGMENT SETS ARE 3SUM-HARD
• Polygon containment under translation
• Polynomial time algorithms for maximizing the intersection volume of polytopes
• Rotational polygon containment and minimum enclosure using only robust 2D constructions
• Translational packing of arbitrary polytopes

Cited in

(1)

• Linear time algorithm to cover and hit a set of line segments optimally by two axis-parallel squares

This page was built for publication: Scandinavian thins on top of cake: new and improved algorithms for stacking and packing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q489760)