Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
This is not algebraic geometry. –  J.C. Ottem Sep 28 '11 at 16:51
    
And what is a chirotope? –  Igor Rivin Sep 28 '11 at 18:00
1  
A chirotope is an oriented matriod. The equivalence was proved by J. Lawrence in 1982. –  Joseph O'Rourke Sep 28 '11 at 19:50
    
There's a reasonable question here, but I suggest you edit in more background and definitions as to make the question more accessible. See e.g. mathoverflow.net/howtoask#motivation . And given the connections between oriented matroid theory and algebraic geometry (studied say by Gel'fand, MacPherson, ...), I wouldn't be too surprised if there was actually some algebraic geometry motivation for this, but it should be edited into the question too. –  j.c. Sep 29 '11 at 2:13
1  
I apologize for the unmotivated question. I am new to MathOverflow and still am not sure how much background information is wanted and useful. –  André Sep 29 '11 at 11:51

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.