---

Geschrieben von Rumpfi am 07.06.2011 um 11:09:

  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