×

Disk packing for the estimation of the size of a wire bundle. (English) Zbl 1126.52300

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. 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.

MSC:

52C22 Tilings in \(n\) dimensions (aspects of discrete geometry)
52C26 Circle packings and discrete conformal geometry
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] J.H. Conway and N.J.A. Sloane, Sphere Packing, Lattice and Groups (Third Edition). Springer-Verlag, New York, 1999. · Zbl 0915.52003
[2] Z. Drezner and E. Erkut, Solving the continuousp-dispersion problem using non-linear programming. J. Oper. Res. Soc.,46 (1995), 516–520. · Zbl 0830.90088
[3] M. Goldberg, Packing of 18 equal circles on a sphere. Elements of Mathematics,20 (1965), 59–61. · Zbl 0129.37502
[4] M. Goldberg, The packing of equal circles in a square. Mathematical Magazine,43 (1970), 24–30. · Zbl 0188.55004 · doi:10.2307/2688107
[5] M. Goldberg, Packing of 14, 16, 17 and 20 circles in a circle. Mathematical Magazine,44 (1971), 134–139. · Zbl 0212.54504 · doi:10.2307/2688222
[6] 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. · Zbl 0901.52017 · doi:10.1016/S0012-365X(97)00050-2
[7] 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. · Zbl 0969.68161 · doi:10.1016/S0167-8396(01)00050-4
[8] 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. · Zbl 0969.68162 · doi:10.1016/S0167-8396(01)00051-6
[9] S. Kravitz, Packing cylinders into cylindrical containers. Mathematical Magazine,40 (1967), 65–71. · Zbl 0192.28801 · doi:10.2307/2688509
[10] D.T. Lee and R.L. Drysdale, III, Generalization of Voronoi diagrams in the plane. SIAM J. Comput.,10 (1981), 73–87. · Zbl 0454.68083 · doi:10.1137/0210006
[11] B.D. Lubachevsky and R.L. Graham, Curved hexagonal packings of equal disks in a circle. Discrete and Computational Geometry,18 (1997), 179–194. · Zbl 0881.52010 · doi:10.1007/PL00009314
[12] B.D. Lubachevsky and F.H. Stillinger, Geometric properties of random disk packing. J. Statist. Phys.,60 (1990), 561–583. · Zbl 1086.82569 · doi:10.1007/BF01025983
[13] M. Mollard and C. Payan, Some progress in the packing of equal circles in a square. Discrete Mathematics,84 (1990), 303–307. · Zbl 0715.52005 · doi:10.1016/0012-365X(90)90135-5
[14] 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. · Zbl 0880.90116 · doi:10.1007/PL00009306
[15] 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. · Zbl 0877.52010
[16] G.E. Reis, Dense packing of equal circles within a circle. Mathematical Magazine,48 (1975), 33–37. · Zbl 0297.52014 · doi:10.2307/2689291
[17] M. Sharir, Intersection and closest-pair problems for a set of planar disks. SIAM J. Comput.,14 (1985), 448–468. · Zbl 0564.68052 · doi:10.1137/0214034
[18] 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.
[19] K. Sugihara and M. Iri, A robust topology-oriented incremental algorithm for Voronoi diagrams. Internat. J. Computational Geometry and Applications,4 (1994), 179–228. · Zbl 0820.68126 · doi:10.1142/S0218195994000124
[20] G. Valette, A better packing of ten circles in a square. Discrete Mathematics,76 (1989), 57–59. · Zbl 0672.52007 · doi:10.1016/0012-365X(89)90288-4
[21] 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. · Zbl 0628.68042 · doi:10.1007/BF02187890
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.