DENSITY OF RANGE CAPTURING HYPERGRAPHS

Abstract. For a finite set X of points in the plane, a set S in the plane, and a positive integer k, we say that a k-element subset Y of X is captured by S if there is a homothetic copy S ′ of S such that X ∩ S ′ = Y, i.e., S ′ contains exactly k elements from X. A k-uniform S-capturing hypergraph H = H(X,S, k) has a vertex set X and a hyperedge set consisting of all k-element subsets of X captured by S. In case when k = 2 and S is convex these graphs are planar graphs, known as convex distance function Delaunay graphs. In this paper we prove that for any k ≥ 2, any X, and any convex compact set S, the number of hyperedges in H(X,S, k) is at most (2k − 1)|X|+ O(k2). Moreover, this bound is tight up to an additive O(k2) term. This refines a general result of Buzaglo, Pinchasi and Rote [2] stating that every pseudodisc topological hypergraph with vertex set X has O(k2|X|) hyperedges of size k or less