Overblog Suivre ce blog
Editer l'article Administration Créer mon blog


29 septembre 2008 1 29 /09 /septembre /2008 20:29

Voici la question du lundi  diffusée aujourd'hui sur le site de Les mathématiques.net

La " question du lundi " n°4, 29 septembre 2008: " Kissing numbers " !

Ami(e)s du lundi et des autres jours, Bonjour;


Un de mes amis (anglophone), Keerthi, m'interroge au sujet des "kissing numbers" :


"Recently I have undergone a course on optimization and there was one problem which the professor had asked us to solve. The problem is well known as "Kissing Number" Problem. To start with I would like to work on the two dimensional space and the geometric elements of circles with uniform shape with the same diameter. In this case the Kissing Number is the number of adjusent circles whose surfaces touch each other but which are not overlapping. From intusion we could say the kissing number is 6 as we could form the circles by keeping their center as the vertex of the hexogonal and one more circle in the center of the hexogonal. There can be 7 partcipating circles and 6 surfaces in contact which means 6 is the kissing numbers possible.


But I would like to formulate the kissing number problem as an equation to be solved using optimisation techniques. That means there shall be an equation which would have the property to be maximised. That is in this case Kissing number, and there will be constraints which will restrict this maximisation like no overlapping condition.


In my idea, the parameters for this formulation are; Uniform Circles with diameter d are identified by Cx, where x = 0 to N. This implies the kissing number is N and the centered circle is C0. If the two uniform circles touch each other then the distance between their centers shall be d, which is the diameter of these circles. Distance is an function with parameters (Cx, Cy), where x not equal to y and the value of the distance shall be equal to d. I got to prove N is 7.


Constraint 1:

For i = 1 to N

Distance(C0, Ci) = d


Constraint 2:

For j = 1 to N

For k = 1 to N and j is not equal to k

Distance(Cj, Ck) >= d


Constraint 1 = is neighbourhood condition for the centered circle C0, and Constraint 2 is non overlapping condition between all the participating circles. I guess the maxmization parameter here is N.


Geometrically I would like to use the formulas so that I could maximize N. I do not know if I have to use the circumference of the circle to identify the remaining space on the surface of the circle C0 to place another circle. Spatially I could imagine circle C0 located at the origin (0, 0). Then I can consider the first Kissing point of (0, r) where the circle C0 and C1 touch each other. Now my problem comes how mathematically I could place the second circle C2 which touches both C0 and C1 at one point each. My problem is also to identify an optimization technique which I could use to solve this problem.


Could you be able to provide me some hints in solving this problem? "


Could you be able to provide us some hints in solving Keerthi’s problem ? 



Pour participer à la discussion




Partager cet article

Repost 0
Published by Norbert Verdier - dans Question Du Lundi
commenter cet article


Articles Récents