Counting the interior points of a point configuration

DOI10.1007/PL00009483MaRDI QIDQ1961848zbMATH OpenFDO

Authors Victor Reiner, Paul Edelman

Publication date 30 January 2000

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/PL00009483

zbMATH Keywords

convex geometriesmatroid invariantspoint configuration

Mathematics Subject Classification ID

Configuration theorems in linear incidence geometry (51A20) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40)

Review text

Let \(A\) be a collection of points in \(\mathbb{R}^d\) whose affine span is \(\mathbb{R}^d\), and \(\text{int}(A)\) the set of points in \(A\) that lie in the interior of its convex hull \(\text{conv}(A)\). A subset \(K\subseteq A\) is called free if \(\text{conv} (K)\cap A=K\) and the set of vertices of \(\text{conv}(K)\) is \(K\). The authors prove that \[ \bigl|\text{int}(A) \bigr|= (-1)^{d-1} \sum_{K \text{free}} (-1)^{|K|} |K|, \] a recent conjecture of Ahrens, Gordon, and McMahon, by showing that this formula can be interpreted as a sum of Euler characteristics of certain complexes associated with \(A\), and then computing the homology of these complexes. This method extends to other examples of convex geometries.

Recommendations

• On the topology of the free complexes of convex geometries
• Interior points of the convex hull of few points in \(\mathbb{E}^ d\)
• Inclusion-exclusion principles for convex hulls and the Euler relation
• On the existence of a point subset with 4 or 5 or \(k\) interior points
• On the existence of a point subset with a specified number of interior points

Cited in

(14)

• On the NBC-complexes and \(\beta \)-invariants of abstract convex geometries
• Expected rank in antimatroids
• Convexity and the beta invariant
• An Euler relation for valuations on polytopes
• On weighted sums of numbers of convex polygons in point sets
• Linear relations for a generalized Tutte polynomial
• On empty convex polygons in a planar point set
• Inclusion-exclusion principles for convex hulls and the Euler relation
• The max-flow min-cut property of two-dimensional affine convex geometries
• When bad things happen to good trees
• Noncrossing partition lattices from planar configurations
• The affine representation theorem for abstract convex geometries
• On the topology of the free complexes of convex geometries
• Local topology of the free complex of a two-dimensional generalized convex shelling

This page was built for publication: Counting the interior points of a point configuration

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