A fast way to test whether a partial function can be extended to a chirotope of rank 3 ?

2011-09-28T15:53:46Z

Hello,

What is a fast way to test whether a partial function can be extended to a chirotope of rank 3 ? That is: I have a domain

$E = \{1,...,n\}$

and a partial function

$f: E^3 \to \{-1, 0, 1\}$

and want to check, whether $f$ can be extended to a total function on $E^3$ so that for every $k \in E$ and every $a, b, c, d \in E\setminus \{k\}$ the set

$\{f(k,a,b) \cdot f(k,c,d), -f(k,a,c) \cdot f(k,b,d), f(k,a,d) \cdot f(k,b,c)\}$

either contains $\{-1,1\}$ or it equals $\{0\}$ .

Motivation: I am studying qualitative spatial relation algebras, especially the Flip Flop (aka LeftRight) Calculus, which describes the position of a point C in the plane with respect to two points A and B using the relations »left«, »right«, »front«, »back«, »inside«, »start« (where C=A), »end« (where C=B) and two special relations »dou« (where A=B≠C) and »tri« (where A=B=C). Given a set of points and relations between some of those points, i want to find out, whether that configuration is realizable.

Only considering »left«, »right« and »inline« (which subsumes the relations »back«, »front« and »inside«; the remaining relations are not considered) a set of such constraints is equivalent to a partial function $f$ as defined above. A total function that satisfies the condition above (which is derived from a 3-term Grassmann-Plücker identity) and whose absolute value $|f|$ is a matroid is by definition a chirotope which is equivalent to an oriented matroid and also to a pseudoline arrangement. The problem, whether a given set of points - and relations »left«, »right« or »inline« between ALL of them - is realizable is equivalent to the realizability problem for matroids and also equivalent to the stretchability problem for pseudolines.

Since pseudoline arrangements with up to 8 lines are always stretchable, testing whether the partial function $f$ can be extended to a chirotope gives a decision procedure for my problem with up to 8 points.

For further reading i suggest the paper »Oriented Matroids« by Jürgen Richter-Gebert and Günter M. Ziegler.

A fast way to test whether a partial function can be extended to a chirotope of rank 3 ? - MathOverflow

A fast way to test whether a partial function can be extended to a chirotope of rank 3 ?