Loading...
Loading...

Go to the content (press return)

On circles enclosing many points

Author
Claverol, M.; Huemer, C.; Martínez, A.
Type of activity
Presentation of work at congresses
Name of edition
XVIII Spanish Meeting on Computational Geometry
Date of publication
2019
Presentation's date
2019-07-02
Book of congress proceedings
XVIII Spanish Meeting on Computational Geometry: book of abstracts: Girona, July 1-3, 2019
First page
51
Last page
54
Project funding
2017SGR1640
Combinatorics of networks and computation
Discrete and Combinatorial Geometry (DCG) Gen. Cat. DGR 2017SGR1336
Geometry and graphs: interactions and applications
Repository
http://imae.udg.edu/egc2019/doc/BookAbstractsEGC2019.pdf Open in new window
Abstract
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...
Keywords
Circle containment, Discrete geometry, Point set, Voronoi diagram
Group of research
CGA -Computational Geometry and Applications
DCG - Discrete and Combinatorial Geometry

Participants