Alors dans une partie bornee du plan (on va dire un carre) je vous donne des points et je vous dit qu'ils ont ete choisis aleatoirement sur une figure prealablement tracee sur ladite partie. Quel est selon vous "la meilleure approximation de la figure" que l'on peut faire. Et surtout comment defineriez vous ce terme.

(je precise que j'en ai aucune idee, je repondrais pas ce soir )

Il est 5h30 du mat

Le 19 juillet 2016 à 09:10:25 bluepoint_ a écrit :
Ça ressemble un peu au problème du tank allemand

d'apres ce que je viens de lire on dispose d'une variable aleatoire, le but retrouvee la loi qu'elle suit sachant qu'elle est dans un ensemble de loi fixee (dans l'exemple uniforme). Le pb ici, c'est que si on se limite a des lois uniformes sur les ensembles de mesures non nuls (par exemple) les meilleurs loi seront les loi uniformes sur des regions de type union de petites superficies chaqune contenant 1 point indique. C'est pas vraiment le resultat qu'on attendrait (limite aux uniforme sur des connexes ne fait guere mieux)

Ce papier a l'air de répondre à peu près à ta question, regarde à partir de la page 12 : http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.103.6770&rep=rep1&type=pdf

Le 19 juillet 2016 à 10:38:55 Hachino a écrit :
Ce papier a l'air de répondre à peu près à ta question, regarde à partir de la page 12 : http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.103.6770&rep=rep1&type=pdf

merci mais de ce que je viens de voir c'est pour des surfaces fines:
The neighboring points of P∗ are nearly on a line bon la ici non

Le 19 juillet 2016 à 11:52:50 bluepoint_ a écrit :

C'est pas vraiment le resultat qu'on attendrait

Bah sans hypothèses sur ta figure et justement sans définir ce qu'est une "bonne approximation" comme tu le fais remarquer, tu peux pas dire que c'est pas le résultat qu'on attendrait, ou alors tu peux le dire pour n'importe quel résultat

Ce n'est pas un pb mathematique mais un probleme de mathematisation. J'ai un debut de reponse . Imaginons les point decrivent "naturellement" un carre. A aire fixee qu'est ce qui distingue ledit carre d'une union de petites surfaces chacunes contenant un point: le perimetre. A aire fixee la solution naturelle est je pense celle contenant tout les points ayant le plus petit perimetre.

Si tu veux minimiser le périmètre et que tes points sont sur la frontière (c'est pas dit très clairement, mais ça a l'air d'être ça), la solution sera donnée par un polygone passant par les points dans l'ordre qui minimise le périmètre sur toutes les permutations possibles de points. (Oui c'est glouton.) Si tes points peuvent être à l'intérieur, tu prends l'enveloppe convexe et le polygone aura pour sommets les points sur le bord de l'enveloppe.

Ça m'a l'air raisonnable.

Le 19 juillet 2016 à 13:12:34 Hachino a écrit :
Si tu veux minimiser le périmètre et que tes points sont sur la frontière (c'est pas dit très clairement, mais ça a l'air d'être ça), la solution sera donnée par un polygone passant par les points dans l'ordre qui minimise le périmètre sur toutes les permutations possibles de points. (Oui c'est glouton.) Si tes points peuvent être à l'intérieur, tu prends l'enveloppe convexe et le polygone aura pour sommets les points sur le bord de l'enveloppe.

Ça m'a l'air raisonnable.

ah ouai intuitivement on aurait tendance a dessine la figure un peu plus grosse mais quand le nombre de point devient eleve et que la figure est pas trop tordu ca doit quand meme donne qqchose de pas mal (par contre non pour l'envollope convexe si la figure est possiblement tordue, en forme d'etoile par exemple)

(par contre non pour l'envollope convexe si la figure est possiblement tordue, en forme d'etoile par exemple)

Bien vu, si tu tires tes points dans une fractale alors que ta vraie figure est beaucoup plus simple (faut vraiment pas avoir de chance quand même), t'as probablement intérêt à grossir le trait, si j'ose dire.

hum
reste 1petit pb:
on a vu qu' a aire fixe la sol est la surface (qui sera donc une union de polygone) ayant le + petit perim mais comment comparer deux figures ayant 2 aires differentes ?

Beh justement, à toi de fixer ton critère. Tu peux choisir un critère mixte si tu veux, genre argmin(a*per^2 + b*aire) pour avoir quelque chose d'homogène, à supposer qu'il existe nécessairement au moins un minimum dans ces conditions.

nah un truc naturel peut etre un truc du style par homotethie si je multiplie le perimetre par x alors je mutiplie l'aire par x² donc un critere naturel serait Perimetre²/Aire (le score ne tend pas vers 0 quand la figure devient grosse ou petite)

Si la figure test est astreinte à contenir les points en un sens quelconque, le score ne peut pas tendre vers 0.

Edit : au moins sous l'hypothèse a,b \neq 0, sinon on peut ptet gruger avec des étoiles très piquées.

Le 19 juillet 2016 à 13:46:29 Hachino a écrit :
Si la figure test est astreinte à contenir les points en un sens quelconque, le score ne peut pas tendre vers 0.

soit x1...xn des points fixes prenont la notation Perimetre^3/Aire prenont Xk la figure (non connexe) compose de n boule centre succisivement sur x1....xn de rayon 1/k alors tout les Xk contiennent tout les points et score(Xk) ->0

Je sais pas trop ce que tu désires, mais à vue de nez si tu as assez de points et pas de bruit (tu es sûr que les points sont exactement sur la frontière de ta figure), tu peux considérer que chaque point A est relié à son plus proche voisin B et à son deuxième plus proche voisin C tel que A, B et C ne sont pas alignés. Tu traces les segments AB et AC pour tous les A et ça te donne un polygone assez satisfaisant avec une complexité en n^2

Le 19 juillet 2016 à 13:56:24 Morphisme a écrit :
Je sais pas trop ce que tu désires, mais à vue de nez si tu as assez de points et pas de bruit (tu es sûr que les points sont exactement sur la frontière de ta figure), tu peux considérer que chaque point A est relié à son plus proche voisin B et à son deuxième plus proche voisin C tel que A, B et C ne sont pas alignés. Tu traces les segments AB et AC pour tous les A et ça te donne un polygone assez satisfaisant avec une complexité en n^2

ca peut etre une union de polygone

Edit : mci bcp tlm je vais manger

Qu'est-ce que tu désignes par "ça" ?