voila j'ai du mal à créer ma procédure maple pour mon tipe, si quelqu'un pouvait m'aider, voici le sujet :
Étant donner 2n points du plan trouver une droite qui sépare le plan en deux parties contenant chacun n points.
Je suis preneur de tout conseils
merci
Bonjour.
Les points sont répartis au hasard ? Limités dans un espace fermé ?Étant donner 2n points du plan
Oui les points sont répartis au hasard, il faut a priori faire appelle à un algorithme de tri mais je ne parviens pas à comprendre comment faire.
Je pense qu'il y a une infinité de droites.
Le plus simple est de calculer la médiane (sur x ou y) puis de tracer la droite (verticale ou horizontale)
Salut,
Moi je te conseille de projeter sur une direction que tu choisis aléatoirement de façon uniforme parmi toutes les directions possibles. Tu as alors une probabilité nulle de tomber sur une mauvaise direction (une mauvaise direction c'est une direction telle que après projection des points sont confondus, ex: la direction horizontale s'il y a des points verticalements alignés). La droite de séparation est alors perpendiculaire à la direction sur laquelle tu as projeté.
Une fois projeté tu te ramène au problème en dimension 1 et la solution c'est la médiane qu'on peut calculer en triant les valeurs. Le coup total est en O(n ln n). Je l'ai fait en scilab ca marche à tous les coups.
Sinon si tu ne veux pas utiliser d'aléatoire il faut d'abord calculer toutes les valeurs interdites de direction, mais c'est en O(n^2), il faut regarder tous les couples de points possibles, la direction de la droite qui passe par les deux points est interdite. Je l'ai fait aussi en scilab, mais ça ne marche que pour une vingtaine de points maxi, faute de mémoire puisqu'il faut stocker les directions interdites et il y en a de l'ordre de n^2, et donc on dépasse assez rapidement les capacités mémoire alors qu'avec un choix de direction aléatoire on peut le faire pour 2000 points facilement.
