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

DOI10.1016/J.EJC.2009.03.010MaRDI QIDQ1039428zbMATH OpenOpenAlexFDO

Authors Oswin Aichholzer, David Orden, J. García-López, Pedro Ramos

Publication date 30 November 2009

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0801.1036

zbMATH Keywords

\((\leq k)\)-edge\((\leq k)\)-facet\(k\)-facetnumber of convex quadrilateralsrectilinear crossing numbersimplicial half-net

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Erd?s problems and related topics of discrete geometry (52C10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

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

Review text

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\).

Recommendations

• New results on lower bounds for the number of (⩽ k)-facets
• Lower bound for the maximal number of facets of a 0/1 polytope
• Bounding the number of k-faces in arrangements of hyperplanes
• scientific article; zbMATH DE number 5555978
• New lower bounds for the number of \((\leq k)\)-edges and the rectilinear crossing number of \(K_{n}\)
• Upper bounds for the number of facets of a simplicial complex
• scientific article; zbMATH DE number 1205994
• A bound on the k-gonality of facets of the hypermetric cone and related complexity problems
• Upper bounds on the maximal number of facets of 0/1-polytopes
• New bounds on the \(k\)-domination number and the \(k\)-tuple domination number

Cites work

• -nets and simplex range queries
• A lower bound for the rectilinear crossing number
• Circles through two points that always enclose many points
• Graph Drawing
• scientific article; zbMATH DE number 4032498 (Why is no real title available?)
• scientific article; zbMATH DE number 2145237 (Why is no real title available?)
• New lower bounds for the number of \((\leq k)\)-edges and the rectilinear crossing number of \(K_{n}\)
• Research Problems in Discrete Geometry

Cited in

(7)

• Bounding the number of k-faces in arrangements of hyperplanes
• \(k\)-sets and rectilinear crossings in complete uniform hypergraphs
• How many simplices are needed to triangulate a Grassmannian?
• Energy Considerations for the Stabilization of Constrained Mechanical Systems with Velocity Projection
• New results on lower bounds for the number of (⩽ k)-facets
• Entering and leaving \(j\)-facets
• Deep cliques in point sets

This page was built for publication: New results on lower bounds for the number of \((\leq k)\)-facets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1039428)