A combinatorial property of convex sets (Q1355195): Difference between revisions

A known result in combinatorial geometry states that in any set \(P_n\) of \(n\) points in the plane there are two elements such that any circle containing them contains \(n/c\) elements of \(P_n\), \(c\) a constant. This has already previously been generalized to higher dimensions. Here the authors prove a generalization of the original result in a different direction. The set \(P_n\) is replaced by a family \(\Phi \) of \(n\) noncrossing compact convex sets, and ''circle'' is replaced by ''homethetic image of a fixed strictly convex compact set \(S\)''. By constructing a counterexample they show that the word ''noncrossing'' must not be omitted, and that the analogue in higher dimensions does not even hold for families of disjoint compact convex sets. The proof is based on a new kind of Voronoi diagram, the so-called ''closest covered set Voronoi diagram'', where each point \(x\) of the plane belongs to the cell of the first element of \(\Phi \) contained in an expanding homothetic image of \(S\) centered at \(x\).