Background
----------


Considering a set of points $(x\_i, y\_i)$ in $\mathbb R^2$ and constraints between some triples of them, which state, whether the three points of the triple are oriented clockwise (R), counter-clockwise (L) or collinear (I), we can translate this into a set of inequalities of the form


$x\_1 y\_2 - x\_1 y\_3 - x\_2 y\_1 + x\_2 y\_3 + x\_3 y\_1 - x\_3 y\_2 < 0$


$x\_1 y\_2 - x\_1 y\_3 - x\_2 y\_1 + x\_2 y\_3 + x\_3 y\_1 - x\_3 y\_2 > 0$


$x\_1 y\_2 - x\_1 y\_3 - x\_2 y\_1 + x\_2 y\_3 + x\_3 y\_1 - x\_3 y\_2 = 0$


for (R), (L) and (I) respectively, where the polynomials on the left-hand side are obtained from the determinant


$\det \begin{pmatrix}
1 & x\_1 & y\_1 \newline
1 & x\_2 & y\_2 \newline
1 & x\_3 & y\_3
\end{pmatrix}
= \begin{pmatrix}
x\_2 - x\_1 \newline y\_2 - y\_1
\end{pmatrix}
\cdot \begin{pmatrix}
y\_3 - y\_1 \newline x\_1 - x\_3
\end{pmatrix}
$.




---


So the set of constraints is satisfiable iff the corresponding system of (in-)equalities is satisfiable.
Although this problem is NP-hard, i am interested in the following:



> 
> What is a (relatively) fast way to decide satisfiability of such a system of (in-)equalities?
> 
> 
> 


Kind regards.



A fast way to decide satisfiability of a set of simple fewnomial inequalities?
I believe your problem is NP-hard.
If you had, not just triples-constraints for *some* triples, but had given the
orientation of *every* triple, then you have specified what is known as the combinatorial *order type*
of the point configuration. (See [Handbook of Discrete and Computational Geometry](http://www.crcpress.com/product/isbn/9781584883012), Chapter 5,
"Pseudoline arrangements.") This is equivalent (in some sense) to a rank-3 [oriented matroid](http://en.wikipedia.org/wiki/Oriented_matroid#Geometry).
It is NP-hard to determine whether or not an oriented matroid is realizable by points in $\mathbb{R}^2$. This was established in a 1991 paper by Peter Shor, "Stretchability of pseudolines is NP-hard"
([PDF link](http://math.mit.edu/~shor/papers/Stretchability_NP-hard.pdf)).
Jürgen Richter-Gebert's Ph.D. thesis was on this topic:
"On the realizability problem of combinatorial geometries—Decision methods," 1992.


**Update**. To respond to the request for more specific information, let me suggest
Günter Ziegler's 1996 article, "Oriented Matroids Today" ([PDF link](http://www.combinatorics.org/Surveys/ds4.pdf)), Section 3.4, "Realization algorithms," where he says,



> 
> the most eﬃcient algorithm (in practice) currently available to ﬁnd a realization (if one exists) 
>  is the iterative “rubber band” algorithm described in Pock [532].
> 
> 
> 


As you can infer from the number 532, this article has a comprehensive bibliography!


I might also recommend looking at Aichholzer et al.'s 2001 paper,
"[Enumerating Order Types for Small Point Sets with Applications](http://dl.acm.org/citation.cfm?id=378596),"
which includes a clear exposition of the relationship between order types and
pseudoline arrangements. Oswin Aichholzer maintains a very nice [Order Type web page](http://www.ist.tugraz.at/staff/aichholzer//research/rp/triangulations/ordertypes/), which
is worth visiting for the latest information. There you will learn that there are exactly
2,334,512,907 order types of 11-point sets.


