Dénombrement de points dans un espace de dimension N

[mlelorra]

Bonjour

J'aimerais trouver ici de l'aide pour orienter ma recherche mais je ne connais pas a priori la formulation mathématique du problème.

De façon concrète,

Soit un point X appartenant à N*n (espace des entiers naturels de dimension n où n<=8)
Je cherche à dénombrer tous les points de N*n tel que la "distance" entre le point X et chacun des autres points soit inférieur ou égale à K

--> qui peut me guider vers une formulation mathématique de cela ?

Ps: en dimension 1, 2 ou 3, j'arrive à appréhender l'espace en question (respectivement un segment, un disque et une boule) et donc à me donner une idée de la chose (sans pour autant arriver au dénombrement autrement que sur l'espace de dimension 1...)

Merci par avance

[trust]

Peut-être parce que ça fait trop longtemps que je n'ai pas fait de math donc j'ai un peu du mal à saisir. Quand tu parles de N*n, c'est bien cet espace-ci : ?

[mlelorra]

Peut-être parce que ça fait trop longtemps que je n'ai pas fait de math donc j'ai un peu du mal à saisir. Quand tu parles de N*n, c'est bien cet espace-ci : ?

Euuhh... effectivement, je me suis peut-être mal exprimé
N = les entiers naturels
n = la dimension

Par exemple N*2 serait l'ensemble des points dont les composantes X et Y sont des entiers positifs soient les couples (0,0), (0,1), (5,8), (12,4) par exemple

[chan79]

Euuhh... effectivement, je me suis peut-être mal exprimé
N = les entiers naturels
n = la dimension

Par exemple N*2 serait l'ensemble des points dont les composantes X et Y sont des entiers positifs soient les couples (0,0), (0,1), (5,8), (12,4) par exemple

N*2 ou N*8 ?

[adrien69]

Salut,
Alors si c'est pour la distance euclidienne c'est chiant, mais si c'est pour la distance de la norme sup c'est tranquille non ?

[trust]

Pour n = 1, tu en as dénombré combien ?
Sinon, K est-il entier ou pas ? Tu considères quelle distance ?

[mlelorra]

Pour n = 1, tu en as dénombré combien ?
Sinon, K est-il entier ou pas ? Tu considères quelle distance ?

pour dimension 1, je suis à 2K + 1

K est bien entier naturel également

Pour la définition de distance, c'est assez empirique mais je ne sais pas comment la définir mathématiquement

[adrien69]

pour dimension 1, je suis à 2K + 1

C'est faux. Tu es dans
Fais juste un petit schéma, tu verras pourquoi c'est faux.

Pour ce qui est de la distance, je ne sais pas comment la définir mathématiquement

C'est bien le problème, il y a plein de façons différentes de la définir, qui se valent presque toutes. Sauf qu'il y en a une qui permet de résoudre facilement ton problème et d'autres qui le rendent compliqué.

[mlelorra]

C'est faux. Tu es dans
Fais juste un petit schéma, tu verras pourquoi c'est faux.

Alors là, je sèche. J'ai bien fait le schéma et je trouve bien 2K+1
Ou alors c'est que je me suis mal exprimé une nouvelle fois

Par exemple si je prends , le point (4) et K = 2.
Mon segment sera délimité par les points (4-2) = (2) et (4+2) = (6)
J'aurais donc l'ensemble des points {(2),(3),(4),(5),(6)}
et le cardinal de cet ensemble est bien 5 (soit 2 * 2 + 1)

C'est bien le problème, il y a plein de façons différentes de la définir, qui se valent presque toutes. Sauf qu'il y en a une qui permet de résoudre facilement ton problème et d'autres qui le rendent compliqué.

Désolé, là aussi je sèche. Quelles seraient les définitions possibles ?

ps: j'ai oublié de préciser que mes souvenirs mathématiques sont fort fort lointains... je "bosse" dans une équipe d'informaticien et je me replonge dans qq règles mathématiques dans le cadre d'une mission très ponctuelle d'algorithmie

[adrien69]

Par exemple si je prends , le point (4) et K = 2.

Prends K=6 et le point (4) tu verras où ça coince.

Quelles seraient les définitions possibles ?

Eh bien imagine que tu es dans (on prend direct le cas le plus bizarre)
Un point x de s'écrit avec pour tout i.

Tu peux alors définir une distance d sur par

ou encore

pareil pour tout

mais tu peux aussi définir


Mais à la vue de ce que tu as dit à la toute fin de ton post j'ai une question, tu veux résoudre le problème mathématiquement ou informatiquement ?

[mlelorra]

Prends K=6 et le point (4) tu verras où ça coince.

Effectivement, mais disons que je voyais ça comme un cas "particulier".

Qui dans les hypothèses à ma dispo pour mon problème n'arrivera(it) pas

Mais à la vue de ce que tu as dit à la toute fin de ton post j'ai une question, tu veux résoudre le problème mathématiquement ou informatiquement ?

C'est bien informatiquement
L'idée est que je trouve rapidement une solution la plus proche possible de mon objectif (sans forcément être sûr à 100% d'avoir LA solution)

[mlelorra]

C'est bien le problème, il y a plein de façons différentes de la définir, qui se valent presque toutes. Sauf qu'il y en a une qui permet de résoudre facilement ton problème et d'autres qui le rendent compliqué.

Toutes les définitions se valent ?

Car de mon côté, en réfléchissant un peu, je me suis dit :
- sur dimension 1, ce sont les points "entiers" d'un segment
- sur dimension 2, ce sont les points aux coordonnées "entières" d'un disque
- sur dimension 3, ce sont les points aux coordonnées "entières" dans une boule

J'ai donc intuité que sur dimension n, ce sont les points aux coordonnées "entières" dans une n-sphère.
J'ai donc cherché une formule générique. Et plus précisément, la mesure de Lebesgue Mesure de Lebesgue

Par approximation, je me dis que cette mesure (notamment pour des grandes valeurs de K = le rayon) est proche du cardinal de mon ensemble de points aux coordonnées entières

Est-ce que ces réflexions se tiennent ? ou fais-je fausse route ?

Merci

[chan79]

Toutes les définitions se valent ?

Car de mon côté, en réfléchissant un peu, je me suis dit :
- sur dimension 1, ce sont les points "entiers" d'un segment
- sur dimension 2, ce sont les points aux coordonnées "entières" d'un disque
- sur dimension 3, ce sont les points aux coordonnées "entières" dans une boule

J'ai donc intuité que sur dimension n, ce sont les points aux coordonnées "entières" dans une n-sphère.
J'ai donc cherché une formule générique. Et plus précisément, la mesure de Lebesgue Mesure de Lebesgue

Par approximation, je me dis que cette mesure (notamment pour des grandes valeurs de K = le rayon) est proche du cardinal de mon ensemble de points aux coordonnées entières

Est-ce que ces réflexions se tiennent ? ou fais-je fausse route ?

Merci

bonjour
pas sûr que ce soit utile mais pour n=2, quand R devient très grand, le quotient du nombre de points par R² a l'air de tendre vers (ci-dessous pour R=1000)

[img][IMG]http://img593.imageshack.us/img593/4136/26266231.gif[/img]

pour n=3, le quotient par R³ tend vers

[raph107]

bonjour
pas sûr que ce soit utile mais pour n=2, quand R devient très grand, le quotient du nombre de points par R² a l'air de tendre vers (ci-dessous pour R=1000)

[img][IMG]http://img593.imageshack.us/img593/4136/26266231.gif[/img]

pour n=3, le quotient par R³ tend vers

Bonjour,

Quand k est assez grand, pour la norme euclidienne, le nb de points à l'interieur de la boule est voisin du volume de cette boule donc tes résultats sont cohérents
Pour n = 1 le nb de points est voisin de 2k
Pour n = 2 le nb de points est voisin de
Pour n = 3 le nb de points est voisin de
Pour n = 4 le nb de points est voisin de
et ainsi de suite.

Le site suivant donne l'expression du volume d'une sphère dans :
http://fr.wikipedia.org/wiki/N-sph%C3%A8re

[mlelorra]

Bonjour,

Quand k est assez grand, pour la norme euclidienne, le nb de points à l'interieur de la boule est voisin du volume de cette sphère donc tes résultats sont cohérents
Pour n = 1 le nb de points est voisin de 2k
Pour n = 2 le nb de points est voisin de
Pour n = 3 le nb de points est voisin de
Pour n = 4 le nb de points est voisin de
et ainsi de suite.

Le site suivant donne l'expression du volume d'une sphère dans :
http://fr.wikipedia.org/wiki/N-sph%C3%A8re

Cool ! il y a donc bien une logique dans ma réflexion !!!

La question étant de savoir si la "mesure" du rayon que j'utilise est conforme à la représentation que j'ai de mon problème tel qu'exprimé

Ps: j'avais trouvé le même lien pour la N-sphère (et qui m'a mené à la mesure de Lebesgue)

[raph107]

Cool ! il y a donc bien une logique dans ma réflexion !!!

La question étant de savoir si la "mesure" du rayon que j'utilise est conforme à la représentation que j'ai de mon problème tel qu'exprimé

Ps: j'avais trouvé le même lien pour la N-sphère (et qui m'a mené à la mesure de Lebesgue)

La mesure de Lebesgue est la norme euclidienne:
Dans R la mesure de Lebesgue d'un intervalle est sa longueur, dans R^n la mesure d'un pavé est égale au produit des longueurs de ses côtés.

Pour l'approximation du nb de points par le volume, on peut approximer le volume de la boule par la somme des volumes unitaires des pavés unitaires centrés en chacun des points.

[mlelorra]

La mesure de Lebesgue est la norme euclidienne:
Dans R la mesure de Lebesgue d'un intervalle est sa longueur, dans R^n la mesure d'un pavé est égale au produit des longueurs de ses côtés.

Pour l'approximation du nb de points par le volume, on peut approximer le volume de la boule par la somme des volumes unitaires des pavés unitaires centrés en chacun des points.

Pas sûr d'avoir tout compris désolé !

Et j'avoue que le coup du pavé me trouble

Aussi, pouvez-vous juste me confirmer que cette mesure me donnerait bien une approximation de ma recherche ?

Merci

[chan79]

Pas sûr d'avoir tout compris désolé !

Et j'avoue que le coup du pavé me trouble

Aussi, pouvez-vous juste me confirmer que cette mesure me donnerait bien une approximation de ma recherche ?

Merci

Pour compléter, pour n=2, il existe une formule connue qui donne le nombre de points à coordonnées entières situés dans un disque fermé de rayon avec k entier
c'est le nombre 1 + 4(k - [k/3] + [k/5] - [k/7] + ...)
avec [ ] = partie entière
Pour k=8 par exemple
1+4(8-2+1-1)=25

[raph107]

Pas sûr d'avoir tout compris désolé !

Et j'avoue que le coup du pavé me trouble

Aussi, pouvez-vous juste me confirmer que cette mesure me donnerait bien une approximation de ma recherche ?

Merci

Oui c'est bien la mesure de Lebesgue. Pour comprendre le remplissage de la boule par des pavés voici quelques exemples concrets:
Pour n = 1, un pavé unitaire est un intervalle de longueur 1
Pour n = 2, un pavé unitaire est un carré de coté 1
Pour n = 3, un pavé unitaire est un cube d'arrête 1

Si on prend le 3 ème exemple et si on trace des cubes de coté 1 et de centre les points de coordonnées entières à l'interieur de la boule, on couvre bien toute la boule et on a même l'inégalité:
nb de points >= volume puisque certains pavés unitaires ont une partie à l'exterieur de la boule et le nombre des pavés est égal au nb de points.

[mlelorra]

Pour compléter, pour n=2, il existe une formule connue qui donne le nombre de points à coordonnées entières situés dans un disque fermé de rayon avec k entier
c'est le nombre 1 + 4(k - [k/3] + [k/5] - [k/7] + ...)
avec [ ] = partie entière
Pour k=8 par exemple
1+4(8-2+1-1)=25

héhé, merci !
Aurais tu la "version" de cette formule pour N = 5 et N = 8 ?

ps: j'aime bien le "formule connue"