A fast way to test whether a partial function can be extended to a chirotope of rank 3 ? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T06:09:03Z http://mathoverflow.net/feeds/question/76657 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/76657/a-fast-way-to-test-whether-a-partial-function-can-be-extended-to-a-chirotope-of-r A fast way to test whether a partial function can be extended to a chirotope of rank 3 ? weltensegler 2011-09-28T15:53:46Z 2011-09-29T11:49:35Z <p>Hello,</p> <p>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</p> <p><code>$E = \{1,...,n\}$</code></p> <p>and a partial function</p> <p><code>$f: E^3 \to \{-1, 0, 1\}$</code></p> <p>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 <code>$a, b, c, d \in E\setminus \{k\}$</code> the set</p> <p><code>$\{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)\}$</code></p> <p>either contains <code>$\{-1,1\}$</code> or it equals <code>$\{0\}$</code>.</p> <p>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.</p> <p>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.</p> <p>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.</p> <p>For further reading i suggest the paper »Oriented Matroids« by Jürgen Richter-Gebert and Günter M. Ziegler.</p>