Cross-Sections of Line Configurations in R-3 and (D-2)-Flat Configurations in R-D

We consider sets L = {l(1),..., l(n)} of n labeled lines in general position in R-3, and study the order types of point sets {p(1),..., p(n)} that stem from the intersections of the lines in L with (directed) planes Pi, not parallel to any line of L, that is, the proper cross-sections of L. As two main results, we show that the number of different order types that can be obtained as cross-sections of G is O(n(9)) when considering all possible planes Pi, and O(n3) when restricting considerations to sets of pairwise parallel planes, where both bounds are tight. The result for parallel planes implies that any set of n points in R-2 moving with constant (but possibly different) speeds along straight lines forms at most O(n(3)) different order types over time. We further generalize the setting from R-3 to R-d with d > 3, showing that the number of order types that can be obtained as cross-sections of a set of n labeled (d - 2)-flats in Rd with planes is O ((((n3) + n)(d(d-2)))). (C) 2018 Elsevier B.V. All rights reserved.