Orientations of triples of points in the plane

Question

Given a finite indexing-set $I$ and a collection $P = \{P_i: \ i \in I\}$ of points in the plane no three of which are collinear, let $I_{(3)}$ denote the set of ordered triples of distinct elements of $I$, and let $f_P$ be the function from $I_{(3)}$ to $\{1,-1\}$ such that $f_P(i,j,k)$ is 1 (resp. $-1$) if the points $p_i,p_j,p_k$ lie in counterclockwise (resp. clockwise) order on the circle going through the three points. Call an $f$ that is of the form $f_P$ for some $P$ “achievable”. Is achievability a local condition, in the sense that there exists a fixed $k$ with the property that a function $f: I_{(3)} \rightarrow \{1,-1\}$ is achievable iff its restriction to $I’_{(3)}$ is achievable for all $k$-element subsets $I’ \subseteq I$?

The smallest unachievable $f$, with $|I|=4$, has $f(1,2,3)=f(1,4,2)=f(2,4,3)=f(3,4,1)$ (associated with the faces of a tetrahedron). To see why it can’t be achieved, note that the three lines through $P_1$, $P_2$, and $P_3$ divide the plane into seven regions; the specified $f$ would correspond to points in the eighth, nonexistent region.

This question is a sharpened version of my earlier question Axiomatizing orientation in the complex plane somewhat in the spirit of the question Arrangements of points in the plane .

Answer 1

If I understand your function correctly, this is the so called „order type“ of a point set, introduced by Goodman and Pollack, see e.g. this survey, which also contains the references to everything that I mention in the following. The question is now whether there is a number k s.t. if for order type of size n every partial order type of size k is realizable, then the whole order type is realizable.

My short answer: probably not

The slightly longer version: I believe I have seen a construction of a non-realizable order type of size n where every partial order type of size n-1 is realizable. However, I dis not find this construction anymore, so I might be confusing it with a different setting. If I find it later, I will update my answer.

There are also other reasons for my „probably not“-answer. The first is that deciding whether an order type is realizable is NP-hard as shown by Shor (in fact, Mnëv has shown that it is ETR-hard, that is, the question whether a system of polynomial equations and inequalities has a solution in the reals is reducible in polynomial time to the question whether an irder type is realizable). If the above number k would exist, it would imply a polynomial time algorithm for order type realizability, proving P=NP=ETR.

There is also the related setting of allowable sequences, which is the setting in yor second related question Arrangements of points in the plane. In this setting, there is an example of a configuration that is not realizable, but every subconfiguration is, see Theorem 2.1 and Figure 2.3 in the survey by Goodman and Pollack. If you allow for collinearities (taking the value 0 in your function), this construction can be adapted to order types by placing additional points at the intersections of the „diagonals“.