Abstract
A heuristic method for packing disks in a circle is constructed, and is applied to the estimation of the sizes of holes through which given sets of electric wires are to pass. Modern intelligent machines such as planes and cars have a variety of electric systems, and consequently a lot of electric wires run in a complicated way. These wires should pass through holes opened in the walls of the body of a machine. Those wholes should be as small as possible because larger holes weaken the body. The problem of finding the smallest hole is reduced to the problem of finding the smallest circle containing all of given disks without overlap. In the proposed method, a sufficiently large circle is initially constructed, and it is shrunk step by step while keeping all the disks inside. For this purpose a Voronoi diagram for circles is used. Computational experiments show the validity and the efficiency of the method.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
J.H. Conway and N.J.A. Sloane, Sphere Packing, Lattice and Groups (Third Edition). Springer-Verlag, New York, 1999.
Z. Drezner and E. Erkut, Solving the continuousp-dispersion problem using non-linear programming. J. Oper. Res. Soc.,46 (1995), 516–520.
M. Goldberg, Packing of 18 equal circles on a sphere. Elements of Mathematics,20 (1965), 59–61.
M. Goldberg, The packing of equal circles in a square. Mathematical Magazine,43 (1970), 24–30.
M. Goldberg, Packing of 14, 16, 17 and 20 circles in a circle. Mathematical Magazine,44 (1971), 134–139.
R.L. Graham, B.D. Lubachevsky, K.J. Nurmela and P.R.T. Östergård, Dense packing of congruent circles in a circle. Discrete Mathematics,181 (1998), 139–154.
D.-S. Kim, D. Kim and K. Sugihara, Voronoi diagram of a circle set from Voronoi diagram of a point set, I. Topology. Computer Aided Geometric Design,18 (2001), 541–562.
D.-S. Kim, D. Kim and K. Sugihara, Voronoi diagram of a circle set from Voronoi diagram of a point set, II. Geometry. Computer Aided Geometric Design,18 (2001), 563–585.
S. Kravitz, Packing cylinders into cylindrical containers. Mathematical Magazine,40 (1967), 65–71.
D.T. Lee and R.L. Drysdale, III, Generalization of Voronoi diagrams in the plane. SIAM J. Comput.,10 (1981), 73–87.
B.D. Lubachevsky and R.L. Graham, Curved hexagonal packings of equal disks in a circle. Discrete and Computational Geometry,18 (1997), 179–194.
B.D. Lubachevsky and F.H. Stillinger, Geometric properties of random disk packing. J. Statist. Phys.,60 (1990), 561–583.
M. Mollard and C. Payan, Some progress in the packing of equal circles in a square. Discrete Mathematics,84 (1990), 303–307.
K.J. Nurmela and P.R.J. Östergard, Packing up to 50 equal circles in a square. Discrete and Computational Geometry,18 (1997), 111–120.
A. Okabe, B. Boots, K. Sugihara and S.-N. Choi, Spatial Tessellations — Concepts and Applications of Voronoi Diagrams (2nd Edition). John Wiley and Sons, Chichester, 2001.
G.E. Reis, Dense packing of equal circles within a circle. Mathematical Magazine,48 (1975), 33–37.
M. Sharir, Intersection and closest-pair problems for a set of planar disks. SIAM J. Comput.,14 (1985), 448–468.
K. Sugihara and M. Iri, VORONOI2 Reference Manual—Topology-oriented Version of the Incremental Methods for Constructing Voronoi Diagrams (2nd Edition). Dept. of Math. Eng., Univ. of Tokyo, 1993.
K. Sugihara and M. Iri, A robust topology-oriented incremental algorithm for Voronoi diagrams. Internat. J. Computational Geometry and Applications,4 (1994), 179–228.
G. Valette, A better packing of ten circles in a square. Discrete Mathematics,76 (1989), 57–59.
C. Y. Yap, An O(n logn) algorithm for the Voronoi diagram of a set of simple curve segments. Discrete and Computational Geometry,2 (1987), 365–393.
Author information
Authors and Affiliations
About this article
Cite this article
Sugihara, K., Sawai, M., Sano, H. et al. Disk packing for the estimation of the size of a wire bundle. Japan J. Indust. Appl. Math. 21, 259–278 (2004). https://doi.org/10.1007/BF03167582
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF03167582