Thema: Konvexe Hülle |
|
Ich hab folgende Problemstellung:
Ich hab eine Menge A mit n Punkten in einer Ebene. Die Konvexe Hülle aus A besteht aus O( sqrt(log(n)) ) Punkten.
Man soll aus dieser Angabe einen Algorithmus entwickeln, der diese Konvexe Hülle berechnet, aber ich hab Schwierigkeiten, diese Angabe zu verstehen.
Ich kann es mir nur so vorstellen, dass A aus zB 512 Punkten besteht, und die Konvexe Hülle dadurch aus 3 Punkten besteht (Informatik hat immer Basis 2 für Logarithmen). Aber wenn die Hülle aus diesem Beispiel nur aus 3 Punkten besteht, gibt es ja über 20 Millionen Möglichkeiten, oder versteh ich da was falsch.
lg Rumpfi
|
|
Thema: Fließkommazahlen |
|
Das Problem liegt daran, dass die Zahl ziemlich klein ist.
Ich kann dir den Tipp geben, zu logarithmieren. Deine gesuchte Potenz kannst du mit folgender Formel suchen:
-1,4 *10^(-45) = 2^x
Mit etwas Matheverständnis weißt du, wie deine Exponente ausschauen wird und dann kannst du die Mantisse angehen.
|
|
|