Realization of abstract convex geometries by point configurations (Q1041213)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Realization of abstract convex geometries by point configurations |
scientific article |
Statements
Realization of abstract convex geometries by point configurations (English)
0 references
1 December 2009
0 references
A convex geometry is a closure space \((J,\bar{\text{ }})\) satisfying the anti-exchange axiom: If \(x\in \overline{A\cup \{y\}}\) and \(x\notin A\) then \(y\notin \overline{A\cup \{x\}}\) for all \(x\neq y\) in J and all closed \(A\subset J.\) A set \(X\subseteq \mathbb{R}^{n}\) induces a convex geometry \((X,\bar{\text{ }})\) by setting \(\overline{Y}=\mathrm{conv}(Y)\cap X\) for \(Y\subseteq X,\) where \(\mathrm{conv}(Y)\) denotes standard convex hull. A problem posed in [\textit{P. H. Edelman} and \textit{R. E. Jamison}, Geom. Dedicata 19, 247--270 (1985; Zbl 0577.52001)] is to characterize those convex geometries induced by sets \(X\) in the plane. The authors show that the Edelman-Jamison Problem modified by requiring preservation of a fixed circular ordering is equivalent to the NP-hard Order Type Problem of determining whether a given function from the triples of distinct members of a set \(J\) into \(\{-1,1\}\) can be realized as the function of orientation for a suitable configuration of \(|J|\) points in the plane. They also discuss the relationship between the realization problem for convex geometries and a similar problem for oriented matroids.
0 references
convex geometries
0 references
point configurations
0 references
oriented matroids
0 references