Online Circle Packing
Authors:
- Sándor P. FeketeSFSándor P. Fekete
- Sven von HövelingSHSven von Höveling
- Christian SchefferCSChristian Scheffer
Preprint
Abstract
We consider the online problem of packing circles into a square container. A sequence of circles has to be packed one at a time, without knowledge of the following incoming circles and without moving previously packed circles. We present an algorithm that packs any online sequence of circles with a combined area not larger than 0.350389 0.350389 of the square's area, improving the previous best value of {\pi}/10 \approx 0.31416; even in an offline setting, there is an upper bound of {\pi}/(3 + 2 \sqrt{2}) \approx 0.5390. If only circles with radii of at least 0.026622 are considered, our algorithm achieves the higher value 0.375898. As a byproduct, we give an online algorithm for packing circles into a 1\times b rectangle with b \geq 1. This algorithm is worst case-optimal for b \geq 2.36.Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- Split Packing: Algorithms for Packing Circles with Optimal Worst-Case DensityDiscrete & Computational Geometry, 2018
- Solving circle packing problems by global optimization: Numerical results and industrial applicationsEuropean Journal of Operational Research, 2008
- A New Verified Optimization Technique for the "Packing Circles in a Unit Square" ProblemsSIAM Journal on Optimization, 2005
- Disk packing for the estimation of the size of a wire bundleJapan Journal of Industrial and Applied Mathematics, 2004
- Packing equal circles in a square: a deterministic global optimization approachDiscrete Applied Mathematics, 2002
- Integrated container loading software for pulp and paper industryEuropean Journal of Operational Research, 1994
- Packing squares into a squareJournal of Parallel and Distributed Computing, 1990
- Some packing and covering theoremsColloquium Mathematicum, 1967
- The Densest Packing of 9 Circles in a SquareCanadian Mathematical Bulletin, 1965