Skip to main content

2019 | OriginalPaper | Buchkapitel

On the Thinnest Covering of Fixed Size Containers with Non-euclidean Metric by Incongruent Circles

verfasst von : Alexander Kazakov, Anna Lempert, Quang Mung Le

Erschienen in: Mathematical Optimization Theory and Operations Research

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

The paper is devoted to the circle covering problem with unequal circles. The number of circles is given. Also, we know a function, which determines a relation between the radii of two neighboring circles. The circle covering problem is usually studied in the case when the distance between points is Euclidean. We assume that the distance is determined by means of some special metric, which, generally speaking, is not Euclidean. The special numerical algorithm is suggested and implemented. It based on optical-geometric approach, which is developed by the authors in recent years and previously used only for circles of the equal radius. The results of a computational experiment are presented and discussed.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literatur
1.
Zurück zum Zitat Al-Sultan, K., Hussain, M., Nizami, J.: A genetic algorithm for the set covering problem. J. Oper. Res. Soc. 47(5), 702–709 (1996)MATHCrossRef Al-Sultan, K., Hussain, M., Nizami, J.: A genetic algorithm for the set covering problem. J. Oper. Res. Soc. 47(5), 702–709 (1996)MATHCrossRef
2.
Zurück zum Zitat Azimi, Z., Toth, P., Galli, L.: An electromagnetism metaheuristic for the unicost set covering problem. Eur. J. Oper. Res. 205(2), 290–300 (2010)MathSciNetMATHCrossRef Azimi, Z., Toth, P., Galli, L.: An electromagnetism metaheuristic for the unicost set covering problem. Eur. J. Oper. Res. 205(2), 290–300 (2010)MathSciNetMATHCrossRef
3.
Zurück zum Zitat Bánhelyi, B., Palatinus, E., Lévai, B.: Optimal circle covering problems and their applications. CEJOR 23(4), 815–832 (2015)MathSciNetMATHCrossRef Bánhelyi, B., Palatinus, E., Lévai, B.: Optimal circle covering problems and their applications. CEJOR 23(4), 815–832 (2015)MathSciNetMATHCrossRef
5.
Zurück zum Zitat Brusov, V., Piyavskii, S.: A computational algorithm for optimally covering a plane region. USSR Comput. Math. Math. Phys. 11(2), 17–27 (1971)CrossRef Brusov, V., Piyavskii, S.: A computational algorithm for optimally covering a plane region. USSR Comput. Math. Math. Phys. 11(2), 17–27 (1971)CrossRef
6.
Zurück zum Zitat Conway, J., Sloane, N.: Sphere Packing. Lattices and Groups. Springer Science and Business Media, New York (1999)CrossRef Conway, J., Sloane, N.: Sphere Packing. Lattices and Groups. Springer Science and Business Media, New York (1999)CrossRef
7.
Zurück zum Zitat Dorninger, D.: Thinnest covering of the euclidean plane with incongruent circles. Anal. Geom. Metr. Spaces 5(1), 40–46 (2017)MathSciNetMATHCrossRef Dorninger, D.: Thinnest covering of the euclidean plane with incongruent circles. Anal. Geom. Metr. Spaces 5(1), 40–46 (2017)MathSciNetMATHCrossRef
8.
Zurück zum Zitat Florian, A., Heppes, A.: Solid coverings of the euclidean plane with incongruent circles. Discrete Comput. Geom. 23(2), 225–245 (2000)MathSciNetMATHCrossRef Florian, A., Heppes, A.: Solid coverings of the euclidean plane with incongruent circles. Discrete Comput. Geom. 23(2), 225–245 (2000)MathSciNetMATHCrossRef
10.
Zurück zum Zitat Fodor, F.: The densest packing of 12 congruent circles in a circle. Beitr. Algebra Geom. 41(2), 401–409 (2000)MathSciNetMATH Fodor, F.: The densest packing of 12 congruent circles in a circle. Beitr. Algebra Geom. 41(2), 401–409 (2000)MathSciNetMATH
11.
Zurück zum Zitat Fodor, F.: The densest packing of 13 congruent circles in a circle. Contrib. Algebra Geom. 44(2), 431–440 (2003)MathSciNetMATH Fodor, F.: The densest packing of 13 congruent circles in a circle. Contrib. Algebra Geom. 44(2), 431–440 (2003)MathSciNetMATH
14.
15.
Zurück zum Zitat Jandl, H., Wieder, A.: A continuous set covering problem as a quasi differentiale optimization problem. Optim. J. Math. Program. Oper. Res. 19(6), 781–802 (1988)MathSciNetMATHCrossRef Jandl, H., Wieder, A.: A continuous set covering problem as a quasi differentiale optimization problem. Optim. J. Math. Program. Oper. Res. 19(6), 781–802 (1988)MathSciNetMATHCrossRef
16.
Zurück zum Zitat Kazakov, A., Lempert, A.: An approach to optimization in transport logistics. Autom. Remote Control 72(7), 1398–1404 (2011)MathSciNetMATHCrossRef Kazakov, A., Lempert, A.: An approach to optimization in transport logistics. Autom. Remote Control 72(7), 1398–1404 (2011)MathSciNetMATHCrossRef
17.
Zurück zum Zitat Kazakov, A., Lempert, A.: On mathematical models for optimization problem of logistics infrastructure. Int. J. Artif. Intell. 13(1), 200–210 (2015) Kazakov, A., Lempert, A.: On mathematical models for optimization problem of logistics infrastructure. Int. J. Artif. Intell. 13(1), 200–210 (2015)
18.
Zurück zum Zitat Kazakov, A., Lempert, A., Le, Q.: An algorithm for packing circles of two types in a fixed size container with non-euclidean metric. In: Supplementary Proceedings of the Sixth International Conference on Analysis of Images, Social Networks and Texts, vol. 1975, pp. 281–292. CEUR-WS (2017) Kazakov, A., Lempert, A., Le, Q.: An algorithm for packing circles of two types in a fixed size container with non-euclidean metric. In: Supplementary Proceedings of the Sixth International Conference on Analysis of Images, Social Networks and Texts, vol. 1975, pp. 281–292. CEUR-WS (2017)
19.
Zurück zum Zitat Kirchner, K., Wengerodt, G.: Die dichteste packung von 36 kreisen in einem quadrat. Beitr. Algebra Geom. 25, 147–159 (1987)MathSciNetMATH Kirchner, K., Wengerodt, G.: Die dichteste packung von 36 kreisen in einem quadrat. Beitr. Algebra Geom. 25, 147–159 (1987)MathSciNetMATH
20.
Zurück zum Zitat Markot, M.: Interval methods for verifying structural optimality of circle packing configurations in the unit square. J. Comput. Appl. Math. 199, 353–357 (2007)MathSciNetMATHCrossRef Markot, M.: Interval methods for verifying structural optimality of circle packing configurations in the unit square. J. Comput. Appl. Math. 199, 353–357 (2007)MathSciNetMATHCrossRef
22.
23.
Zurück zum Zitat Nurmela, K.: Conjecturally optimal coverings of an equilateral triangle with up to 36 equal circles. Exp. Math. 9(2), 241–250 (2000)MathSciNetMATHCrossRef Nurmela, K.: Conjecturally optimal coverings of an equilateral triangle with up to 36 equal circles. Exp. Math. 9(2), 241–250 (2000)MathSciNetMATHCrossRef
25.
Zurück zum Zitat Nurmela, K., Ostergard, P.: Covering a square with up to 30 equal circles. Technical report Res. rept A62., Lab. Technol. Helsinki Univ. (2000) Nurmela, K., Ostergard, P.: Covering a square with up to 30 equal circles. Technical report Res. rept A62., Lab. Technol. Helsinki Univ. (2000)
26.
27.
29.
Zurück zum Zitat Toth, G.: Thinnest covering of a circle by eight, nine, or ten congruent circles. Comb. Comput. Geom. 52, 361–376 (2005)MathSciNetMATH Toth, G.: Thinnest covering of a circle by eight, nine, or ten congruent circles. Comb. Comput. Geom. 52, 361–376 (2005)MathSciNetMATH
30.
Zurück zum Zitat Toth, L.F.: Solid circle-packings and circle-coverings. Studia Sci. Math. Hungar. 3, 401–409 (1968)MathSciNetMATH Toth, L.F.: Solid circle-packings and circle-coverings. Studia Sci. Math. Hungar. 3, 401–409 (1968)MathSciNetMATH
31.
Zurück zum Zitat Ushakov, V., Lebedev, P.: Algorithms of optimal set covering on the planar \({R^2}\). Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki 26(2), 258–270 (2016) Ushakov, V., Lebedev, P.: Algorithms of optimal set covering on the planar \({R^2}\). Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki 26(2), 258–270 (2016)
32.
Zurück zum Zitat Watson-Gandy, C.D.T.: An electromagnetism metaheuristic for the unicost set covering problem. Eur. J. Oper. Res. 205(2), 290–300 (2010)MathSciNetMATHCrossRef Watson-Gandy, C.D.T.: An electromagnetism metaheuristic for the unicost set covering problem. Eur. J. Oper. Res. 205(2), 290–300 (2010)MathSciNetMATHCrossRef
Metadaten
Titel
On the Thinnest Covering of Fixed Size Containers with Non-euclidean Metric by Incongruent Circles
verfasst von
Alexander Kazakov
Anna Lempert
Quang Mung Le
Copyright-Jahr
2019
DOI
https://doi.org/10.1007/978-3-030-33394-2_15