New results on lower bounds for the number of (at most k)-facets

Abstract

In this paper we present three different results dealing with the number of $(\le k)$-facets of a set of points: 1. We give structural properties of sets in the plane that achieve the optimal lower bound $3\left(\genfrac{}{}{0ex}{}{k+2}{2}\right)$ of $(\le k)$-edges for a fixed $0\le k\le \lfloor n/3\rfloor -1$; 2. We give a simple construction showing that the lower bound $3\left(\genfrac{}{}{0ex}{}{k+2}{2}\right)+3\left(\genfrac{}{}{0ex}{}{k-\lfloor \frac{n}{3}\rfloor +2}{2}\right)$ for the number of $(\le k)$-edges of a planar point set appeared in [Aichholzer et al. New lower bounds for the number of ($\le k$)-edges and the rectilinear crossing number of $K_n$. {\em Disc. Comput. Geom.} 38:1 (2007), 1--14] is optimal in the range $\lfloor n/3\rfloor \le k\le \lfloor 5n/12\rfloor -1$; 3. We show that for $k<\lfloor n/(d+1)\rfloor$ the number of $(\le k)$-facets of a set of $n$ points in general position in ${\mathbb{R}}^d$ is at least $(d+1)\left(\genfrac{}{}{0ex}{}{k+d}{d}\right)$, and that this bound is tight in the given range of $k$.

11 pages, 5 figures. Submitted to European Journal of Combinatorics. Changes: last result in the abstract generalized to $d$ dimensions, Section 4 simplified

References in corpus (1)

• New lower bounds for the number of $(\le k)$-edges and the rectilinear crossing number of $K_n$

Cited by in corpus (1)

• $k$-Sets and Rectilinear Crossings in Complete Uniform Hypergraphs