ProV Logo
0
New results on lower bounds for the numb...
Aichholzer, Oswin...

Free

New results on lower bounds for the number of (at most k)-facets by Aichholzer, Oswin ( Author )
Lemonjar Open Access
N.A
07-01-2008
In this paper we present three different results dealing with the number of (≤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) of (≤k)-edges for a fixed 0≤k≤⌊n/3⌋−1; 2. We give a simple construction showing that the lower bound 3(k+22)+3(k−⌊n3⌋+22) for the number of (≤k)-edges of a planar point set appeared in [Aichholzer et al. New lower bounds for the number of (≤k)-edges and the rectilinear crossing number of Kn. {\em Disc. Comput. Geom.} 38:1 (2007), 1--14] is optimal in the range ⌊n/3⌋≤k≤⌊5n/12⌋−1; 3. We show that for k<⌊n/(d+1)⌋ the number of (≤k)-facets of a set of n points in general position in Rd is at least (d+1)(k+dd), and that this bound is tight in the given range of k.
-
Article
pdf
36.88 KB
English
-
MYR 0.00
-
https://arxiv.org/abs/0801.1036
Share this eBook