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

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

2008-01-07

arxiv.org/abs/0801.1036v2

Mathematics

Combinatorics

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

Scientific paper

In this paper we present three different results dealing with the number of $(\leq k)$-facets of a set of points: 1. We give structural properties of sets in the plane that achieve the optimal lower bound $3\binom{k+2}{2}$ of $(\leq k)$-edges for a fixed $0\leq k\leq \lfloor n/3 \rfloor -1$; 2. We give a simple construction showing that the lower bound $3\binom{k+2}{2}+3\binom{k-\lfloor \frac{n}{3} \rfloor+2}{2}$ for the number of $(\leq k)$-edges of a planar point set appeared in [Aichholzer et al. New lower bounds for the number of ($\leq 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 \leq k \leq \lfloor 5n/12 \rfloor -1$; 3. We show that for $k < \lfloor n/(d+1) \rfloor$ the number of $(\leq k)$-facets of a set of $n$ points in general position in $\mathbb{R}^d$ is at least $(d+1)\binom{k+d}{d}$, and that this bound is tight in the given range of $k$.

Affiliated with

Also associated with

No associations

Rating

New results on lower bounds for the number of (at most k)-facets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with New results on lower bounds for the number of (at most k)-facets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and New results on lower bounds for the number of (at most k)-facets will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-654791