5
$\begingroup$

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 .

$\endgroup$
4
  • 4
    $\begingroup$ "no two of which are collinear": Perhaps you mean no three of which are collinear? $\endgroup$ Apr 21, 2020 at 23:28
  • $\begingroup$ I have replaced (geometry) by other tags, this tag is deprecated on MO - see the tag-info. I will also point out that you have linked to the Bjørn Kjos-Hanssen's answer rather than to the question - I am not sure whether that was intentional or it happened by mistake. $\endgroup$ Apr 21, 2020 at 23:39
  • $\begingroup$ @Joseph: I did indeed mean three, not two, and have fixed the text accordingly. Thanks for catching that! $\endgroup$ Apr 22, 2020 at 1:04
  • $\begingroup$ @Martin: That was an error on my part; thanks for catching it. I’ve replaced the link by the one I intended. $\endgroup$ Apr 22, 2020 at 1:07

1 Answer 1

4
$\begingroup$

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“.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.