Top

Published in:

2019 | OriginalPaper | Chapter

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

Authors : Alexander Kazakov, Anna Lempert, Quang Mung Le

Published in: Mathematical Optimization Theory and Operations Research

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

previous chapter Hamilton-Jacobi-Bellman Equations for Non-cooperative Differential Games with Continuous Updating

next chapter The Problem K-Means and Given J-Centers: Polynomial Solvability in One Dimension

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

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

Bánhelyi, B., Palatinus, E., Lévai, B.: Optimal circle covering problems and their applications. CEJOR 23(4), 815–832 (2015)MathSciNetMATHCrossRef

Borovskikh, A.: The two-dimensional eikonal equation. Siberian Math. J. 47(2), 813–834 (2006)MathSciNetMATHCrossRef

Brusov, V., Piyavskii, S.: A computational algorithm for optimally covering a plane region. USSR Comput. Math. Math. Phys. 11(2), 17–27 (1971)CrossRef

Conway, J., Sloane, N.: Sphere Packing. Lattices and Groups. Springer Science and Business Media, New York (1999)CrossRef

Dorninger, D.: Thinnest covering of the euclidean plane with incongruent circles. Anal. Geom. Metr. Spaces 5(1), 40–46 (2017)MathSciNetMATHCrossRef

Florian, A., Heppes, A.: Solid coverings of the euclidean plane with incongruent circles. Discrete Comput. Geom. 23(2), 225–245 (2000)MathSciNetMATHCrossRef

Fodor, F.: The densest packing of 19 congruent circles in a circle. Geom. Dedicata. 74(2), 139–145 (1999)MathSciNetMATHCrossRef

10.

Fodor, F.: The densest packing of 12 congruent circles in a circle. Beitr. Algebra Geom. 41(2), 401–409 (2000)MathSciNetMATH

11.

Fodor, F.: The densest packing of 13 congruent circles in a circle. Contrib. Algebra Geom. 44(2), 431–440 (2003)MathSciNetMATH

12.

Friedman, E.: Circles covering squares. http://www2.stetson.edu/~efriedma/circovsqu/. Accessed 7 Feb 2019

13.

Heppes, A., Melissen, J.: Covering a rectangle with equal circles. Periodica Math. Hung. 34, 65–81 (1997)MathSciNetMATHCrossRef

14.

Heppes, A., Melissen, J.: Covering a rectangle with equal circles. Periodica Math. Hung. 34(1–2), 65–81 (1997)MathSciNetMATHCrossRef

15.

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.

Kazakov, A., Lempert, A.: An approach to optimization in transport logistics. Autom. Remote Control 72(7), 1398–1404 (2011)MathSciNetMATHCrossRef

17.

Kazakov, A., Lempert, A.: On mathematical models for optimization problem of logistics infrastructure. Int. J. Artif. Intell. 13(1), 200–210 (2015)

18.

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.

Kirchner, K., Wengerodt, G.: Die dichteste packung von 36 kreisen in einem quadrat. Beitr. Algebra Geom. 25, 147–159 (1987)MathSciNetMATH

20.

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

21.

Melissen, J.: Densest packings of eleven congruent circles in a circle. Geom. Dedicata. 50, 15–25 (1994)MathSciNetMATHCrossRef

22.

Melissen, J., Schuur, P.: Covering a rectangle with six and seven circles. Discrete Appl. Math. 99, 149–156 (2000)MathSciNetMATHCrossRef

23.

Nurmela, K.: Conjecturally optimal coverings of an equilateral triangle with up to 36 equal circles. Exp. Math. 9(2), 241–250 (2000)MathSciNetMATHCrossRef

24.

Nurmela, K., Ostergard, P.: Packing up to 50 circles in a square. Discrete Comput. Geom. 18, 111–120 (1997)MathSciNetMATHCrossRef

25.

Nurmela, K., Ostergard, P.: Covering a square with up to 30 equal circles. Technical report Res. rept A62., Lab. Technol. Helsinki Univ. (2000)

26.

Stoyan, Y., Patsuk, V.: Covering a compact polygonal set by identical circles. Comput. Optim. Appl. 46, 75–92 (2010)MathSciNetMATHCrossRef

27.

Tarnai, T., Gaspar, Z.: Covering a square by equal circles. Elem. Math. 50, 167–170 (1995)MathSciNetMATH

28.

Toth, G.: Covering the plane with two kinds of circles. Discrete Comput. Geom. 13, 445–457 (1995)MathSciNetMATHCrossRef

29.

Toth, G.: Thinnest covering of a circle by eight, nine, or ten congruent circles. Comb. Comput. Geom. 52, 361–376 (2005)MathSciNetMATH

30.

Toth, L.F.: Solid circle-packings and circle-coverings. Studia Sci. Math. Hungar. 3, 401–409 (1968)MathSciNetMATH

31.

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.

Watson-Gandy, C.D.T.: An electromagnetism metaheuristic for the unicost set covering problem. Eur. J. Oper. Res. 205(2), 290–300 (2010)MathSciNetMATHCrossRef

Title: On the Thinnest Covering of Fixed Size Containers with Non-euclidean Metric by Incongruent Circles
Authors: Alexander Kazakov
Anna Lempert
Quang Mung Le
Publisher: Springer International Publishing
Book: Mathematical Optimization Theory and Operations Research
Print ISBN: 978-3-030-33393-5

Electronic ISBN: 978-3-030-33394-2

Copyright Year: 2019
DOI: https://doi.org/10.1007/978-3-030-33394-2_15

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner