Given two general position point sets in $\mathbb{R}^2$ of the same size and order type, is it possible to continuously move the points of one set until they coincide with those of the other set in such a way that order type is preserved (equivalently, no three points become collinear) throughout the operation?
3
-
1$\begingroup$ It would be nice to have a definition of "order type" here in this question. $\endgroup$– Jeff StromCommented May 29, 2012 at 15:01
-
3$\begingroup$ According to the paper that Nima Hoda links to, the order type of a (finite) set $P$ of points in general position (no 3 are collinear) is a mapping that assigns to each triple $(p,q,r)$ of distinct points in $P$ the orientation of this triple (clockwise, or counterclockwise). (It should be false for infinite sets.) $\endgroup$– GoldsternCommented May 29, 2012 at 16:26
-
$\begingroup$ Yes, Jeff, I should have included the definition for convenience. Thanks for filling that in, Goldstern. $\endgroup$– Nima HodaCommented May 29, 2012 at 20:31
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
I believe the answer is (in general) No for the following reason. A configuration of points in $\mathbb{P}^2$ is projectively dual to an arrangement of lines in $\mathbb{P}^2$. The question you ask, translated to arrangements of lines, is whether an arrangement can always be continuously moved to any isomorphic arrangement, all the while remaining isomorphic. This was asked by Ringle in 1956 (the isotopy conjecture), and answered negatively by Mnev's Universality Theorem in 1985: not only can the space of line arrangments isomorphic to a given arrangement be disconnected, it can have the homotopy type of any algebraic variety.
Of course it is not difficult to change from $\mathbb{P}^2$ to $\mathbb{R}^2$.
I find this explicit claim in a 1988 paper by Suvorov (Springer link):
Here, "nondegenerated" means, I believe, what we would call today "simple": no three lines share a point. A "rigid" isotopy keeps the lines straight (in a "flexible" isotopy, the objects are pseuodolines).
Suvorov's example has 14 lines in $\mathbb{P}^2$. Later (1996) Richter-Gebert found another
14-line/point example, presented in his paper "Two Interesting Oriented Matroids" (CiteSeer link):
He shows that
[its] realization space [...] is an open interval from which one point has been deleted.
answered May 29, 2012 at 20:13
-
$\begingroup$ The OP's question asks specifically about general position point sets -- is there still "universality" after restricting to those? $\endgroup$– j.c.Commented Jul 18, 2017 at 0:26
-
1$\begingroup$ @j.c.: Good question. I think the answer is Yes, but I am not certain. $\endgroup$ Commented Jul 18, 2017 at 10:38
-
2$\begingroup$ Suvorov’s example was in the framwork of activity around Hilbert 16-th problem. The lines configuration was considered as a singular real algebraic curve (obtained as a product of linear equations of the lines. So the term “rigid isotopy” originates in this point of view. $\endgroup$ Commented Mar 22, 2019 at 10:03
-
1$\begingroup$ I wrote a special reply covering the question of @j.c. $\endgroup$ Commented Mar 22, 2019 at 13:16
$\begingroup$
$\endgroup$
The answer is indeed No. The most economic example up to now i think is mentioned Suvorov's. Independently examples was constructed by P. Mani, B. Jaggi, B. Sturmfels, N. White
"Uniform oriented matroids without the isotopy property" (link to pdf)
My perhaps first by time example of simple line arrangement without isotopy property has 19 lines .
I will use language of line arrangements.
As @joseph-orourke correctly guessed in reply to @j.c. the stronger statement holds:
Any open basic semi-algebraic set (i.e the set defined by strict polynomial inequalities with integer coefficients) can be realized up to certain trivial stabilization by realization space of a simple pseudolines arrangement.
It was the initial target theorem due to some applications to Morse theory of vector functions. Reference is N. E. Mnev, "The universality theorems on the classification problem of configuration varieties and convex polytopes varieties" (link to pdf) Theorem A, statement 2). This old paper only briefly describes the content of unpublished phd (link to pdf) in Russian. Unfortunately this moment was not explicitly covered in later improvements and expositions of the proof. But it is really a simple addition to the main construction modernized by P.Shor "Stretchability of pseudolines is NP-hard" (link to pdf), H. Gunzel "The Universal Partition Theorem for Oriented Matroids" (link to pdf) and U. Richter-Gebert "Mne"v's Universality Theorem Revisited" (link to pdf). The point is that having as an input a system of strict algebraic inequalities the general machine produces “constructible” arrangement of pseudolines with realization space equivalent to the open semi-algebraic set defined by the system. “Constructible” means “coming from a free construction using ruler”. It has an order on the pseudolines such that every next is incident to not more then two points in general position defined as intersections of pervious pseudolines. Then such an arrangement can be perturbed to simple with the equivalent realization space by an inductive perurbation trick applied to pseudolines in the reverse order of the construction. The trick was introduced independently by B. Sturmfels and N. White "Constructing uniform oriented matroids without the isotopy property" (link to pdf), see also Shor Lemma 4 (link to pdf) and around.
For completeness i will add that the statement holds for uniform oriented matroids of rank >= 3 . It is not an immediate collary. Very nice reduction of any rank greater than 3 to rank 3 presented by @Arnau
