Vol. 2 (2021): Proceedings of the 3rd BYMAT Conference
Artículos

On circles enclosing many points

Mercè Claverol
Universitat Politècnica de Catalunya
Clemens Huemer
Universitat Politècnica de Catalunya
Alejandra Martínez-Moraian
Universidad de Alcalá
Cover for TEMat monográficos, 2 (2021): Proceedings of the 3rd BYMat Conference

Publicado 28/08/2021

Palabras clave

  • point set,
  • circle containment,
  • Voronoi diagram

Cómo citar

Claverol, Mercè; Huemer, Clemens, y Martínez-Moraian, Alejandra. «On circles enclosing many points». En: TEMat monográficos, 2 (2021): Proceedings of the 3rd BYMAT Conference, págs. 103-105. ISSN: 2660-6003.URL: https://temat.es/monograficos/article/view/vol2-p103.

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.