Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Empilement de cercles
Résumé
vignette|Il n'est pas évident de regrouper des cercles de tailles différentes de la façon la plus compacte.
En géométrie, un empilement de cercles ou empilement de disques est un arrangement de cercles ou de disques, de tailles identiques ou non, dans un domaine donné, de telle sorte qu'aucun chevauchement ne se produise et qu'aucun cercle/disque ne puisse être agrandi sans créer de chevauchement. On se pose à leur sujet divers problèmes comme la recherche d'empilements de densité maximale, ou au contraire, minimale.
Un empilement d'une partie fermée X du plan euclidien dont toute intersection avec un disque est quarrable (i.e. possède une aire), est un ensemble de cercles de rayons non nuls inclus dans X dont les disques fermés associés ont les propriétés suivantes :
deux disques de l'empilement sont tangents ou d'intersection vide,
tout disque est tangent à au moins un autre.
L'empilement est dit localement rigide (localy jammed en anglais) si tout disque est coincé par ses voisins, autrement dit si deux disques tangents à un disque D sans aucun autre disque tangent à D entre eux ont des centres formant un angle aigu avec le centre de D .
L'empilement est dit compact si tout disque tangent à un disque D est tangent à deux autres disques tangents à D ou ce qui est équivalent, si le graphe planaire dont les sommets sont les centres des disques et les arêtes les segments joignant les centres de deux disques tangents a des faces triangulaires .vignette|Empilement complet de cercles dans un triangle.La densité d'un empilement est le rapport de l'aire couverte par les disques à l'aire de la partie X (si X est non bornée, c'est la limite, si elle existe, de la densité de l'intersection avec un disque de rayon tendant vers l'infini).
L'empilement est dit complet si on ne peut lui rajouter de disque, autrement dit si sa densité est égale à 1 .
Un empilement est forcément dénombrable ou fini, tout disque contenant un point à coordonnées rationnelles.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.