Skip to main content
Updated to Handbook 3rd Ed.
Source Link
Joseph O'Rourke
  • 150.9k
  • 36
  • 358
  • 958

Goodman and Pollack called sequences that encapsulate the combinatorics of an arrangement of lines allowable sequences in their classic paper "Semispaces of Configurations, Cell Complexes of Arrangements" (J. Combin. Theory Ser. A, 37:257-293, 1984.) These sequences are equivalent, I believe, to your sequences. (One of GP's theorems is that a sequence of permutations is realizable by points iff it is realizable by lines.) They established the following theorem concerning allowable sequences:

Every allowable sequence of permutations can be realized by an arrangement of pseudolines.

Pseudolines are curves each pair of which intersect exactly once. (More precisely, a pseudoline is a simple closed curve that does not disconnect $\mathbb{P}^2$.) So I think the answer to your question is that the sequences determine pseudoline arrangements, which correspond to "generalized configuration of points," rather than line arrangements, which correspond to configurations of points. Most pseudoline arrangements are not stretchable, i.e., they do not correspond to a line arrangement. So you cannot, in general, reconstruct the point configuration from the sequence. (However, every arrangement of $\le 8$ pseudolines is stretchable, so your efforts can be extended to $i=8$.) There is some work on local conditions with which I am not familar: Felsner and Weil, "Sweeps, Arrangements and Signotopes" (Discrete Applied Math 109:257-267, 2001). Perhaps this is related to your local conditions.

There remains no characterization of stretchability. Peter Shor showed that determining if a pseudoline arrangement is stretchable is NP-hard ("Stretchability of pseudoline arrangements is NP-hard," in Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift, 1991). This certainly accords with your "Alas, it is hard"!

Another source on this topic is Felsner & Goodman's chapter on "Pseudoline Arrangements" in the Handbook of Discrete and Computational GeometryHandbook of Discrete and Computational Geometry (CRC Press, 20043rd Ed., 2017);. Here's a near-final PDF of that link takes you to Google bookschapter: Pseudoline Arrangements. They are also mentioned in the Wikipedia article on arrangements, but a separate article on pseudoline arrangements is yet to be written.

Goodman and Pollack called sequences that encapsulate the combinatorics of an arrangement of lines allowable sequences in their classic paper "Semispaces of Configurations, Cell Complexes of Arrangements" (J. Combin. Theory Ser. A, 37:257-293, 1984.) These sequences are equivalent, I believe, to your sequences. (One of GP's theorems is that a sequence of permutations is realizable by points iff it is realizable by lines.) They established the following theorem concerning allowable sequences:

Every allowable sequence of permutations can be realized by an arrangement of pseudolines.

Pseudolines are curves each pair of which intersect exactly once. (More precisely, a pseudoline is a simple closed curve that does not disconnect $\mathbb{P}^2$.) So I think the answer to your question is that the sequences determine pseudoline arrangements, which correspond to "generalized configuration of points," rather than line arrangements, which correspond to configurations of points. Most pseudoline arrangements are not stretchable, i.e., they do not correspond to a line arrangement. So you cannot, in general, reconstruct the point configuration from the sequence. (However, every arrangement of $\le 8$ pseudolines is stretchable, so your efforts can be extended to $i=8$.) There is some work on local conditions with which I am not familar: Felsner and Weil, "Sweeps, Arrangements and Signotopes" (Discrete Applied Math 109:257-267, 2001). Perhaps this is related to your local conditions.

There remains no characterization of stretchability. Peter Shor showed that determining if a pseudoline arrangement is stretchable is NP-hard ("Stretchability of pseudoline arrangements is NP-hard," in Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift, 1991). This certainly accords with your "Alas, it is hard"!

Another source on this topic is Goodman's chapter on "Pseudoline Arrangements" in the Handbook of Discrete and Computational Geometry (CRC Press, 2004); that link takes you to Google books. They are also mentioned in the Wikipedia article on arrangements, but a separate article on pseudoline arrangements is yet to be written.

Goodman and Pollack called sequences that encapsulate the combinatorics of an arrangement of lines allowable sequences in their classic paper "Semispaces of Configurations, Cell Complexes of Arrangements" (J. Combin. Theory Ser. A, 37:257-293, 1984.) These sequences are equivalent, I believe, to your sequences. (One of GP's theorems is that a sequence of permutations is realizable by points iff it is realizable by lines.) They established the following theorem concerning allowable sequences:

Every allowable sequence of permutations can be realized by an arrangement of pseudolines.

Pseudolines are curves each pair of which intersect exactly once. (More precisely, a pseudoline is a simple closed curve that does not disconnect $\mathbb{P}^2$.) So I think the answer to your question is that the sequences determine pseudoline arrangements, which correspond to "generalized configuration of points," rather than line arrangements, which correspond to configurations of points. Most pseudoline arrangements are not stretchable, i.e., they do not correspond to a line arrangement. So you cannot, in general, reconstruct the point configuration from the sequence. (However, every arrangement of $\le 8$ pseudolines is stretchable, so your efforts can be extended to $i=8$.) There is some work on local conditions with which I am not familar: Felsner and Weil, "Sweeps, Arrangements and Signotopes" (Discrete Applied Math 109:257-267, 2001). Perhaps this is related to your local conditions.

There remains no characterization of stretchability. Peter Shor showed that determining if a pseudoline arrangement is stretchable is NP-hard ("Stretchability of pseudoline arrangements is NP-hard," in Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift, 1991). This certainly accords with your "Alas, it is hard"!

Another source on this topic is Felsner & Goodman's chapter on "Pseudoline Arrangements" in the Handbook of Discrete and Computational Geometry (CRC Press, 3rd Ed., 2017). Here's a near-final PDF of that chapter: Pseudoline Arrangements. They are also mentioned in the Wikipedia article on arrangements, but a separate article on pseudoline arrangements is yet to be written.

Source Link
Joseph O'Rourke
  • 150.9k
  • 36
  • 358
  • 958

Goodman and Pollack called sequences that encapsulate the combinatorics of an arrangement of lines allowable sequences in their classic paper "Semispaces of Configurations, Cell Complexes of Arrangements" (J. Combin. Theory Ser. A, 37:257-293, 1984.) These sequences are equivalent, I believe, to your sequences. (One of GP's theorems is that a sequence of permutations is realizable by points iff it is realizable by lines.) They established the following theorem concerning allowable sequences:

Every allowable sequence of permutations can be realized by an arrangement of pseudolines.

Pseudolines are curves each pair of which intersect exactly once. (More precisely, a pseudoline is a simple closed curve that does not disconnect $\mathbb{P}^2$.) So I think the answer to your question is that the sequences determine pseudoline arrangements, which correspond to "generalized configuration of points," rather than line arrangements, which correspond to configurations of points. Most pseudoline arrangements are not stretchable, i.e., they do not correspond to a line arrangement. So you cannot, in general, reconstruct the point configuration from the sequence. (However, every arrangement of $\le 8$ pseudolines is stretchable, so your efforts can be extended to $i=8$.) There is some work on local conditions with which I am not familar: Felsner and Weil, "Sweeps, Arrangements and Signotopes" (Discrete Applied Math 109:257-267, 2001). Perhaps this is related to your local conditions.

There remains no characterization of stretchability. Peter Shor showed that determining if a pseudoline arrangement is stretchable is NP-hard ("Stretchability of pseudoline arrangements is NP-hard," in Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift, 1991). This certainly accords with your "Alas, it is hard"!

Another source on this topic is Goodman's chapter on "Pseudoline Arrangements" in the Handbook of Discrete and Computational Geometry (CRC Press, 2004); that link takes you to Google books. They are also mentioned in the Wikipedia article on arrangements, but a separate article on pseudoline arrangements is yet to be written.