algorithme pour vérifier si un espace est convexe

est-ce possible de faire en moins de temps polynomial?algorithme pour vérifier si un espace est convexe

2009-06-09 l--' ' ' ' ' ' ---------' ' ' ' ' ' ' ' ' ' ' '

Quel genre d'espace? Sur quelle gamme? La première dérivée n'est pas suffisante? –

Polynôme de quoi? Nombre de points définissant l'espace? – AnnaR

Je pense qu'il veut dire espace métrique, alors comment allez-vous le faire avec un dérivé? –

-2

Hmm ... question intéressante. Je crois que la réponse est oui. En gros, trouvez l'équation plane de chacune des faces; pour chaque paire de faces jointes, si l'angle entre elles est obtus, le volume est concave. Cela devrait fonctionner en O (log (n)).

Je serais prêt à parier qu'il ya une certaine façon de travailler ceci en utilisant un algorithme graphique de coloration, mais je ne suis pas intelligent ...

Source

2009-06-09 17:59:53

D'accord, qu'est-ce qui se passe avec le downvote après que ce soit accepté? –

Comment est-ce nouveau O (log (n))? vous le faites pour chaque avion .. – Yogi

@Yogi: quoi? trouver l'équation du plan pour chaque face est O (1); c'est O (log (n)) car on compare des paires de plans conjoints. Rappelez-vous, trouver l'équation du plan pour un polygone est un temps constant, donc c'est O (1), donc cela n'affecte pas l'ordre global de l'algorithme. –

Utilisez plus de mots.

Nous ne pouvons pas savoir exactement ce que vous demandez. Nous pouvons seulement deviner. Je ne pense pas que les espaces pourraient être convexes ou concaves en général ... peut-être que vous voulez dire le volume ou la superficie? En tout cas, je ne pense pas que vous allez battre le temps polynomial, étant donné que la complexité de la surface va être de nature polynomiale.

Source

2009-06-09 17:54:22 Karl

algorithme pour vérifier si un espace est convexe

Répondre

Questions connexes