Split packing: algorithms for packing circles with optimal worst-case density

DOI10.1007/s00454-018-0020-2zbMath1411.90046arXiv1705.00924OpenAlexW3135993307MaRDI QIDQ1731458

Sebastian Morr, Christian Scheffer, Sándor P. Fekete

Publication date: 13 March 2019

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1705.00924

zbMATH Keywords

approximation algorithmcircle packingworst-case analysis

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Related Items

Packing disks into disks with optimal worst-case density, Descending packing algorithm for irregular graphics based on geometric feature points, Unnamed Item, Packing Geometric Objects with Optimal Worst-Case Density (Multimedia Exposition), Techniques and results on approximation algorithms for packing circles

Uses Software

• packomania
• Split Packing

Cites Work

• Unnamed Item
• Online square-into-square packing
• A literature review on circle and sphere packing problems: models and methodologies
• New approaches to circle packing in a square. With program codes.
• Solving circle packing problems by global optimization: numerical results and industrial applications
• Integrated container loading software for pulp and paper industry
• Packing equal circles in a square: A deterministic global optimization approach
• Disk packing for the estimation of the size of a wire bundle
• An improved algorithm for the packing of unequal circles within a larger containing circle
• Split packing: packing circles into triangles with optimal worst-case density
• On the minimum distance determined by \(n(\leq 7)\) points in an isoscele right triangle
• Polynomial-Time Approximation Schemes for Circle Packing Problems
• Improved Bound for Online Square-into-Square Packing
• Split Packing: An Algorithm for Packing Circles with Optimal Worst-Case Density
• Some packing and covering theorems
• A bounded space algorithm for online circle packing