Publicado 28/08/2021
Palabras clave
- point set,
- circle containment,
- Voronoi diagram
Cómo citar
Esta obra está bajo una licencia internacional Creative Commons Atribución 4.0.
Resumen
Demostramos que en cualquier conjunto de $n$ puntos rojos y $n$ puntos azules en el plano existen un punto rojo y un punto azul tales que cualquier circunferencia que pase por ellos contiene en su interior al menos ${n(1-1/{\sqrt{2}}) -o(n)}$ puntos del conjunto. Esta es una versión bicromática de un problema propuesto por Neumann-Lara y Urrutia. También probamos que todo conjunto $S$ de $n$ puntos en el plano contiene dos puntos tales que cualquier circunferencia que pase por ellos contiene como mucho $\lfloor{\frac{2n-1}{3}}\rfloor$ otros puntos de $S$. Las demostraciones usan propiedades de los diagramas de Voronoi de orden $k$, al estilo del trabajo de Edelsbrunner, Hasan, Seidel y Shen en este problema.