Was sind und was sollen die Pseudogeraden?

(Sorry, couldn't resist the Dedekindesque title.)

I've been arguing about having a frank exchange of views on discussing the proper mathematical definition of pseudolines and pseudoline arrangements with some co-authors, and it seems to be an issue on which there is much confusion. So in hopes of spreading the confusion, I thought I'd discuss it here as well.

To begin with, intuitively, a pseudoline is something that "behaves like" a line, but is not necessarily straight. A pseudoline arrangement is a collection of pseudolines that "behave like" lines, usually meaning that each pair of pseudolines meets in at most a single point of intersection and that when they meet they cross. The concept of a pseudoline arrangement was introduced by F. Levi in 1926. Another important paper in this area was by Ringel in 1956, who showed that there exist pseudoline arrangements that are not combinatorially equivalent to line arrangements.

Usually, a pseudoline arrangement requires all pairs of pseudolines to cross, while a weak pseudoline arrangement (see e.g. de Fraysseix and Ossona de Mendez or one of my papers) allows some pairs to avoid crossing. Weak pseudoline arrangements can model e.g. hyperbolic line arrangements, if one uses a sufficiently general definition of a pseudoline, while non-weak pseudoline arrangements can't.

The difficulty is not so much in the arrangement part, but in the definition of a single pseudoline. Here are some alternatives, roughly ordered from more general to less general.

• De Fraysseix and Ossona de Mendez define a pseudoline to be "an arc homeomorphic to a straight line". I like their paper a lot, but I think this is just a mistake. It allows for open line segments which unlike proper pseudolines do not partition the Euclidean plane into two regions.

• The definition I'd like to use is that a pseudoline is the image of a line under a homeomorphism of the plane to itself. I think this doesn't cause any real difficulties, but it does allow for some strange examples such as the Fermat double spiral. This doesn't seem to be a common choice but apparently it's the one in Shor's 1991 paper on hardness of stretchability; it's also used in at least one more recent manuscript. (ETA: See my follow-up post for a stronger reason to use this definition.)

• Björner et al. in "Oriented Matroids" (1993) (p.257) define an "affine pseudoline" in terms of a topological model of the plane as an open disk. A pseudoline for this model is a simple curve in the closed disk that has its endpoints on the boundary of the disk and all of its other points in the interior of the disk. Björner et al. don't mention, however, how to go from this to a definition of a pseudoline as an object in the Euclidean plane itself. It is tempting to fix a homeomorphism h from the disk to the plane and say that a pseudoline in the plane is the image under this fixed h of a pseudoline in the disk. However, different homeomorphisms give different classes of curves as their pseudolines; for instance, one can find an h that would allow the Fermat spiral as a pseudoline but disallow any line itself to count as a pseudoline. A reasonable choice would be to fix h to be the map that takes polar coordinates \( (r,\theta) \) in the disk to \( (r/(1-r),\theta) \) in the plane, but packing that into the definition leads to something quite unnatural sounding and unwieldy. And while I think that choice of h gives a definition that is invariant under congruence transformations, proving that sort of fact isn't completely obvious. This definition would still work for defining weak pseudoline arrangements, though, and my co-authors like it because we can cite someone else and hope that they've been sufficiently careful in their axiomatics rather than having to get it right ourselves.

• The classical definition from discrete geometry is that a pseudoline is an uncontractible simple closed curve in the projective plane, or equivalently a simple closed curve that does not separate the projective plane. For instance, the nonseparating version is the definition used by Goodman in his pseudoline arrangement chapter of the Handbook of Discrete and Computational Geometry (1997). Grünbaum ("Arrangements and Spreads", 1972) and Kelly and Rottenberg similarly define a pseudoline arrangement to be a collection of simple closed curves in the projective plane such that each pair of curves has exactly one point of intersection, which is equivalent when there are at least two curves in the arrangement. However, these definitions do not allow for weak pseudoline arrangements, as one cannot form nonintersecting pairs of pseudolines.

• A definition I haven't seen used, but one that is very natural when viewing (weak) pseudoline arrangements as the planar duals of zonotopal tilings, is that a pseudoline is a monotone curve: that is, a curve that, when projected perpendicularly onto some line, projects one-to-one. Different pseudolines would be allowed to have different projection lines.

• More popular in computational geometry is the definition that a pseudoline is an \( x \)-monotone curve in the Cartesian plane; that is, it projects one-to-one onto the \( x \) axis, or equivalently is the graph of a continuous function \( y=f(x). \) Edelsbrunner ("Algorithms in Combinatorial Geometry", 1987) uses this definition, for instance, as do Clarkson et al. and Felsner. This definition allows for non-intersecting pairs of pseudolines, but any nonintersecting family of pseudolines is totally ordered by \( y \)-coordinate, and partitions the plane into regions bounded by only two pseudolines, so this is again unsatisfactory for defining weak arrangements.

• Leah Berman (personal communication) suggested a simple combinatorial model of pseudolines, closely related to the projective plane definition, that she says was suggested by Grünbaum: a pseudoline is the result of modifying a Euclidean line by replacing a line segment by a polygonal chain in a non-self-intersecting way. Again, this doesn't work for weak arrangements, but variants of this definition could be made to work: either one can use hyperbolic lines and polygonal chains instead of Euclidean ones, or one can define a pseudoline to be the result of connecting two disjoint Euclidean rays by a polygonal chain having as endpoints the rays' vertices, such that the chain intersects neither itself nor the rays.

• Another simple combinatorial model of pseudolines, introduced by Goodman (1980) and discussed by Felsner, is the "wiring diagram". This model is a special case of the x-monotone definition. In it, the pseudolines are graphs of continuous functions that are constant except within small intervals of the range of x coordinates, within which two functions having values that are adjacent in sorted order swap their values by linear interpolation, forming a crossing. The sorted orders of the pseudolines between the crossings form (half of) a so-called circular sequence of permutations, and wiring diagrams are a convenient device for translating circular sequences into pseudoline arrangemens. Perhaps an illustration might make this description more clear:

A wiring diagram.

I don't have a clear conclusion: while I hope to use the image-of-line-under-homeomorphism-of-plane definition for this publication, I still intend to use others in other situations. In particular, for simplicial arrangements, one needs to use the projective plane, for which the standard discrete geometry definition seems most suited. I guess the overall morals of this story are, first, that sometimes the detailed definitions matter, and it pays to think about which one is best for the problem you're working on. And second, be careful when you're reading papers in this area, because objects that are given the same names might not be the same underneath.

Comments: