We prove that every set of n red and n blue points in the plane contains a red and a blue point such that
every circle through them encloses at least n(1-(1/srqt(2)))-o(n) points of the set. This is a two-colored version of a problem posed by Neumann-Lara and Urrutia. We also show a Ramsey-type result for circles enclosing points. The proofs make use of properties of higher order Voronoi diagrams, in the spirit of the work of Edelsbrunner, Hasan, Seidel and Shen on this topic. Closely related, w...
We prove that every set of n red and n blue points in the plane contains a red and a blue point such that
every circle through them encloses at least n(1-(1/srqt(2)))-o(n) points of the set. This is a two-colored version of a problem posed by Neumann-Lara and Urrutia. We also show a Ramsey-type result for circles enclosing points. The proofs make use of properties of higher order Voronoi diagrams, in the spirit of the work of Edelsbrunner, Hasan, Seidel and Shen on this topic. Closely related, we also study the number of collinear edges in higher order Voronoi diagrams and present several constructions.