| Rumpfi |
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 |
