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

DOI10.1007/s00224-013-9493-9zbMath1303.68143OpenAlexW2093151180MaRDI QIDQ489760

Esther M. Arkin, Helmut Alt, Ferran Hurtado, Irina Kostitsyna, Joseph S. B. Mitchell, Alon Efrat, Valentin Polishchuk, Alexander Kröller, 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

packingcomputational geometryenclosure

Mathematics Subject Classification ID

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

Related Items (1)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A generalization of the convex Kakeya problem
• Finding the upper envelope of n line segments in O(n log n) time
• Geometric Knapsack problems
• Maximizing the overlap of two planar convex sets under rigid motions
• Minimum-perimeter enclosures
• Approximating largest convex hulls for imprecise points
• Translational packing of arbitrary polytopes
• A polynomial solution for the Potato-peeling problem
• Computing the maximum overlap of two convex polygons under translations
• Computing closely matching upper and lower bounds on textile nesting problems
• Rotational polygon containment and minimum enclosure using only robust 2D constructions
• Multiple translational containment. I: An approximate algorithm
• Dense packings of congruent circles in a circle
• Matching convex shapes with respect to the symmetric difference
• Disk packing for the estimation of the size of a wire bundle
• More optimal packings of equal circles in a square
• Maximum overlap of convex polytopes under translation
• Largest bounding box, smallest diameter, and related problems on imprecise points
• Aligning two convex figures to minimize area or perimeter
• Maximum overlap and minimum convex hull of two convex polyhedra under translations
• Faster core-set constructions and data-stream algorithms in fixed dimensions
• Packing a Cake into a Box
• ON COMPUTING ENCLOSING ISOSCELES TRIANGLES AND RELATED PROBLEMS
• Approximating extent measures of points
• Finding Extremal Polygons
• MAXIMIZING THE AREA OF OVERLAP OF TWO UNIONS OF DISKS UNDER RIGID MOTION
• Finding minimal enclosing boxes
• Polygon containment under translation
• Enclosing a Set of Objects by Two Minimum Area Rectangles
• Determining the minimum-area encasing rectangle for an arbitrary closed curve
• Computing and Combinatorics
• POLYGON CONTAINMENT AND TRANSLATIONAL IN-HAUSDORFF-DISTANCE BETWEEN SEGMENT SETS ARE 3SUM-HARD
• On the Minimum Volume Covering Ellipsoid of Ellipsoids
• Discrete and Computational Geometry
• Algorithms and Computation

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