Disposición de puntos en el plano

Question

Sea $p_1,\ldots,p_n$ sea una colección de puntos distintos en $\mathbb{R}^2$ de los cuales tres no se encuentran en una línea. Para cada $p_i$ , dejemos que $\omega_i(p_1,\ldots,p_n)$ sea la siguiente lista ordenada (bien definida hasta la permutación cíclica). Elija alguna dirección $\theta$ de forma que ninguno de los $p_j$ se encuentran en el rayo de $p_i$ yendo en la dirección $\theta$ . Gire $\theta$ en el sentido de las agujas del reloj en un círculo completo, y anote la lista ordenada de los $p_j$ que encuentres. El resultado es $\omega_i(p_1,\ldots,p_n)$ .

Las listas ordenadas de puntos $\omega_i(p_1,\ldots,p_n)$ codifican así parte de la combinatoria de cómo los $p_i$ yacen en el avión.

Mi pregunta es ¿en qué circunstancias se puede ir en la otra dirección? Más concretamente, supongamos que se le da $n$ listas ordenadas $\sigma_1,\ldots,\sigma_n$ donde $\sigma_i$ contiene exactamente los elementos de $\{p_1,\ldots,p_n\} \setminus \{p_i\}$ sin repeticiones y está bien definida hasta permutaciones cíclicas. ¿Cuándo se pueden encontrar puntos $p_1,\ldots,p_n$ en $\mathbb{R}^2$ tal que $\omega_i(p_1,\ldots,p_n) = \sigma_i$ para todos $i$ ?

Es trivial que para $i=1,2,3$ siempre se puede conseguir. Sin embargo, para $i=4$ no es difícil de encontrar $\sigma_i$ como el anterior que no se puede realizar. Por desgracia, es difícil encontrar patrones generales.

He aquí una pregunta/adivinanza algo menos vaga sobre lo que podría ser cierto. Me pregunto si podría haber algún tipo de "condición local" de la siguiente forma. Existe alguna $N$ tal que si $\sigma_1,\ldots,\sigma_n$ es una colección de listas como la anterior, entonces existen puntos $p_1,\ldots,p_n$ como arriba si y sólo si para cada $m$ subconjunto de elementos $S$ de $\{p_1,\ldots,p_n\}$ con $m \leq N$ las listas obtenidas del $\sigma_i$ suprimiendo los puntos no incluidos en $S$ y tirar las listas correspondientes se puede realizar?

Answer 1

Goodman y Pollack llamaron secuencias a las que encapsulan la combinatoria de una disposición de líneas secuencias permitidas en su clásico artículo "Semiespacios de configuraciones, complejos celulares de disposiciones" ( J. Combin. Theory Ser. A , 37:257-293, 1984.) Creo que estas secuencias son equivalentes a las suyas. (Uno de los teoremas de GP es que una secuencia de permutaciones es realizable por puntos si es realizable por líneas). Establecieron el siguiente teorema relativo a las secuencias realizables:

Toda secuencia de permutaciones admisible puede realizarse mediante una disposición de pseudolíneas.

Las pseudolíneas son curvas cuyos pares se cruzan exactamente una vez. (Más concretamente, una pseudolinea es una curva cerrada simple que no desconecta $\mathbb{P}^2$ .) Así que creo que la respuesta a tu pregunta es que las secuencias determinan las disposiciones de las pseudolíneas, que corresponden a "configuraciones generalizadas de puntos", y no a disposiciones de líneas, que corresponden a configuraciones de puntos. La mayoría de los arreglos de pseudolíneas no son estirable es decir, no corresponden a una disposición de líneas. Así que, en general, no se puede reconstruir la configuración puntual a partir de la secuencia. (Sin embargo, toda disposición de $\le 8$ pseudolíneas es extensible, por lo que sus esfuerzos pueden ampliarse a $i=8$ .) Hay algunos trabajos sobre las condiciones locales con los que no estoy familiarizado: Felsner y Weil, " Barridos, arreglos y signotopos " ( Matemáticas aplicadas discretas 109:257-267, 2001). Tal vez esto esté relacionado con sus condiciones locales.

Queda por caracterizar la extensibilidad. Peter Shor demostró que determinar si un arreglo de pseudolíneas es estirable es NP-difícil (" La estirabilidad de los arreglos de pseudolíneas es NP-difícil en Geometría Aplicada y Matemática Discreta: Homenaje a Victor Klee , 1991). Esto concuerda sin duda con su "¡Ay, qué duro es!

Otra fuente sobre este tema es el capítulo de Felsner & Goodman sobre "Pseudoline Arrangements" en el Manual de Geometría Discreta y Computacional (CRC Press, 3ª ed., 2017). Aquí hay un PDF casi final de ese capítulo: Arreglos de pseudolina . También se mencionan en el Artículo de Wikipedia sobre arreglos , pero aún no se ha escrito un artículo aparte sobre las pseudolíneas.

Answer 2

Es una buena pregunta y me gusta tu conjetura sobre la posible forma de una condición local. Me recuerda a varios teoremas sobre conjuntos convexos como Teorema de Helly . Creo ver que una lista ordenada de puntos son los vértices de un polígono convexo (en el orden de las agujas del reloj) exactamente si sus listas restringidas a esos puntos son la misma lista con una supresión. Dado tal polígono convexo también podemos saber qué puntos están dentro de él y cuáles fuera. Yo diría que $N=4$ es suficiente. También que si uno conoce las listas para cada $4$ se pueden reconstruir todos los polígonos convexos. Esto parece deducirse de Teorema de Cartheodory .