View Related Documents

Abstract

Aweaving W is a simple arrangement of lines (or line segments) in the plane together with a binary relation specifying which line is ldquoaboverdquo the other. A system of lines (or line segments) in 3-space is called arealization ofW, if its projection into the plane isW and the ldquoabove-belowrdquo relations between the lines respect the specifications. Two weavings are equivalent if the underlying arrangements of lines are combinatorially equivalent and the ldquoabove-belowrdquo relations are the same. An equivalence class of weavings is said to be aweaving pattern. A weaving pattern isrealizable if at least one element of the equivalence class has a three-dimensional realization. A weaving (pattern)W is calledperfect if, along each line (line segment) ofW, the lines intersecting it are alternately ldquoaboverdquo and ldquobelow.rdquo We prove that (i) a perfect weaving pattern ofn lines is realizable if and only ifn le 3, (ii) a perfect m byn weaving pattern of line segments (in a grid-like fashion) is realizable if and only if min(m, n) le 3, (iii) ifn is sufficiently large, then almost all weaving patterns ofn lines are nonrealizable.

Key words  Line weavings - Lines in space

Communicated by Takao Asano.
Jànos Pach has been supported in part by Hungarian NFSR Grant 1812, NSF Grant CCR-8901484, and the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS), a National Science Foundation Science and Technology Center, under NSF Grant STC88-09648. Richard Pollack has been supported in part by NSA Grant MDA904-89-H-2030, NSF Grants DMS-85-01947 and CCR-8901484, and DIMACS. Emo Welzl has been supported in part by the ESPRIT II Basic Research Actions Program of the EC under Contract No. 3075 (project ALCOM) and DIMACS.

Fulltext Preview

Image of the first page of the fulltext document