Realization of abstract convex geometries by point configurations (Q1041213)

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.