Abstract | ||
---|---|---|
A is a simple arrangement of lines (or line segments) in the plane together with a binary relation specifying which line is “above” the other. A system of lines (or line segments) in 3-space is called a of, if its projection into the plane is and the “above-below” relations between the lines respect the specifications. 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 said to be a A weaving pattern is if at least one element of the equivalence class has a three-dimensional realization. A weaving (pattern) is called if, along each line (line segment) of, the lines intersecting it are alternately “above” and “below.” We prove that (i) a perfect weaving pattern of lines is realizable if and only if ≤ 3, (ii) a perfect m by weaving pattern of line segments (in a grid-like fashion) is realizable if and only if min() ≤ 3, (iii) if is sufficiently large, then almost all weaving patterns of lines are nonrealizable. |
Year | DOI | Venue |
---|---|---|
1993 | 10.1007/BF01190155 | Algorithmica |
Keywords | Field | DocType |
Line weavings,Lines in space | Discrete mathematics,Line segment,Weaving,Computer science | Journal |
Volume | Issue | ISSN |
9 | 6 | 0178-4617 |
ISBN | Citations | PageRank |
0-387-52921-7 | 8 | 0.94 |
References | Authors | |
6 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
János Pach | 1 | 2366 | 292.28 |
Richard Pollack | 2 | 912 | 203.75 |
E. Welzl | 3 | 3311 | 552.52 |