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

preprint2008arXivOpen access

Abstract

In this paper we present three different results dealing with the number of (≤k)(\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(k+22)3\binom{k+2}{2} of (≤k)(\leq k)-edges for a fixed 0≤k≤⌊n/3⌋−10\leq k\leq \lfloor n/3 \rfloor -1; 2. We give a simple construction showing that the lower bound 3(k+22)+3(k−⌊n3⌋+22)3\binom{k+2}{2}+3\binom{k-\lfloor \frac{n}{3} \rfloor+2}{2} for the number of (≤k)(\leq k)-edges of a planar point set appeared in [Aichholzer et al. New lower bounds for the number of (≤k\leq k)-edges and the rectilinear crossing number of KnK_n. {\em Disc. Comput. Geom.} 38:1 (2007), 1--14] is optimal in the range ⌊n/3⌋≤k≤⌊5n/12⌋−1\lfloor n/3 \rfloor \leq k \leq \lfloor 5n/12 \rfloor -1; 3. We show that for k<⌊n/(d+1)⌋k < \lfloor n/(d+1) \rfloor the number of (≤k)(\leq k)-facets of a set of nn points in general position in Rd\mathbb{R}^d is at least (d+1)(k+dd)(d+1)\binom{k+d}{d}, and that this bound is tight in the given range of kk.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.