11

---

Důkaz (jen idea)

správnost

v každé iteraci se vzdálenost rovin d(r_A, r_B) zvětší
obal množiny bodů |A| je konvexní

konečnost

bodů je konečně mnoho

Shrnutí

• nehladká optimalizační úloha
• je-li |A|=m, |B|=n složitost algoritmu řádově K₁(m+n)³, v praxi K₂(m+n)
• v praxi vyžaduje pouze 1 až 5 kroků