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
    0 references
    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

    Identifiers