Arrangement (space partition)

Line arrangements

In discrete geometry, an arrangement is the decomposition of the d-dimesional linear, affine, or projective space into connected open cells of lower dimensions, induced by a finite collection of geometric objects. Sometimes these objects are of the same type, such as hyperplanes or spheres. An interest in the study of arrangements was driven by advances in computational geometry, where the arrangements were unifying structures for many problems. Advances in study of more complicated objects, such as algebraic surfaces, contributed to "real-world" applications, such as motion planning and computer vision. [1]

Types of arrangements by arranged objects

Of particular interest are the arrangements of lines and arrangements of hyperplanes.

A non-stretchable pseudoline arrangement of nine pseudolines. (All arrangements of fewer than nine pseudolines are stretchable.) Per Pappus's hexagon theorem, this arrangement cannot be realized in a projective plane over any field.
A hyperbolic line arrangement combinatorially equivalent to a chord diagram used by Ageev (1996) to show that triangle-free circle graphs may sometimes need 5 colors.


A pseudoline arrangement is a family of curves that share similar topological properties with a line arrangement.[2] These can be defined most simply in the projective plane as simple closed curves any two of which meet in a single crossing point.[3] A pseudoline arrangement is said to be stretchable if it is combinatorially equivalent to a line arrangement; it is complete for the existential theory of the reals to distinguish stretchable arrangements from non-stretchable ones.[4]

Arrangements of hyperbolic lines (lines in the hyperbolic plane) have also been studied. Any finite set of lines in the Euclidean plane has a combinatorially equivalent arrangement in the hyperbolic plane (e.g. by enclosing the vertices of the arrangement by a large circle and interpreting the interior of the circle as a Klein model of the hyperbolic plane). However, in hyperbolic line arrangements lines may avoid crossing each other without being parallel; the intersection graph of the lines in a hyperbolic arrangement is a circle graph. The corresponding concept to hyperbolic line arrangements for pseudolines is a weak pseudoline arrangement,[5] a family of curves having the same topological properties as lines[6] such that any two curves in the family either meet in a single crossing point or have no intersection.

More generally, geometers have studied arrangements of other types of curves in the plane, and of other more complicated types of surface.[7] Arrangements in complex vector spaces have also been studied; since complex lines do not partition the complex plane into multiple connected components, the combinatorics of vertices, edges, and cells does not apply to these types of space, but it is still of interest to study their symmetries and topological properties.[8]

References

  1. ↑ Dan Halperin, "Arrangements", In: Handbook of Discrete and Computational Geometry, 2nd Ed. (2004) ISBN 978-1-58488-301-2
  2. ↑ Grünbaum (1972); Agarwal & Sharir (2002).
  3. ↑ This definition is from Grünbaum (1972). For a comparison of alternative definitions of pseudolines, see Eppstein, Falmagne & Ovchinnikov (2007).
  4. ↑ Shor (1991); Schaefer (2010).
  5. ↑ de Fraysseix & Ossona de Mendez (2003).
  6. ↑ Here an alternative definition from Shor (1991), that a pseudoline is the image of a line under a homeomorphism of the plane, is appropriate.
  7. ↑ Agarwal & Sharir (2000).
  8. ↑ Orlik & Terao (1992).