New results on lower bounds for the number of \((\leq k)\)-facets (Q1039428): Difference between revisions
From MaRDI portal
Changed an Item |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: A lower bound for the rectilinear crossing number / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: New lower bounds for the number of \((\leq k)\)-edges and the rectilinear crossing number of \(K_{n}\) / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Graph Drawing / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Research Problems in Discrete Geometry / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3772828 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Circles through two points that always enclose many points / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: \(\epsilon\)-nets and simplex range queries / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4657586 / rank | |||
Normal rank |
Latest revision as of 06:14, 2 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | New results on lower bounds for the number of \((\leq k)\)-facets |
scientific article |
Statements
New results on lower bounds for the number of \((\leq k)\)-facets (English)
0 references
30 November 2009
0 references
The paper is concerned with lower bounds for the number of \((\leq k)\)-facets of a set of points in a Euclidean space. An oriented simplex with vertices at points of \(S\) is said to be a \((\leq k)\)-facet of \(S\), if it has at most \(k\) points of \(S\) in the positive side of its affine hull. The paper presents two different results dealing with the number of \((\leq k)\)-facets of a set of points: (1) gives 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\); and (2) shows 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\).
0 references
\(k\)-facet
0 references
\((\leq k)\)-facet
0 references
\((\leq k)\)-edge
0 references
rectilinear crossing number
0 references
simplicial half-net
0 references
number of convex quadrilaterals
0 references
0 references