Before revision:  This improves the bound O (n\log n) of Edelsbrunner, Valtr and Welzl from 1997.
After revision:  This improves the bound \Omega (n\log n) of Edelsbrunner, Valtr and Welzl from 1997.