ICS 269, Winter 2000: Theory Seminar

3 March 2000:
Weaving Patterns of Lines and Line Segments in Space
Javid Hüseynov, ICS, UC Irvine

A weaving W is a simple arrangement of lines (or line segments) in the plane together with a binary relation specifying which line is "above" the other. Two weavings are equivalent if the underlying arrangements of lines are combinatorially equivalent and the "above-below" relations are the same. An equivalence class of weavings is called a weaving pattern.

In a perfect weaving pattern, along each line l of W, the lines intersecting it are alternately "above" and "below". This paper discusses the realization of weavings and weaving patterns in 3-space. The authors prove that:

1. A perfect weaving pattern of n lines is realizable iff n<=3
2. A perfect m by n (bipartite) weaving pattern of line segments is realizable iff min(m,n) <= 3
3. If n -> infinity, then almost all weaving patterns are nonrealizable.

(Based on a paper by János Pach, Richard Pollack, and Emo Welzl, in Algorithmica 9:561-571, 1993.)