Cross-sections of line configurations in $R^3$ and $(d\!-\!2)$-flat configurations in $R^d$

O. Aichholzer, R. Fabila-Monroy, F. Hurtado, P. Perez-Lantero, A. J. Ruiz-Vargas, J. Urrutia, and B. Vogtenhuber

Abstract:

We consider sets $\mathcal{L} = \{\ell_1, \ldots, \ell_n\}$ of $n$ labeled lines in general position in ${{\sf l} \kern -.10em {\sf R} }^3$, and study the order types of point sets $\{p_1, \ldots, p_n\}$ that stem from the intersections of the lines in $\mathcal{L}$ with (directed) planes $\Pi$, not parallel to any line of $\mathcal{L}$, that is, the proper cross-sections of $\mathcal{L}$. As two main results, we show that the number of different order types that can be obtained as cross-sections of $\mathcal{L}$ is $O(n^9)$ when considering all possible planes $\Pi$, and $O(n^3)$ 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 ${{\sf l} \kern -.10em {\sf 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 ${{\sf l} \kern -.10em {\sf R} }^3$ to ${{\sf l} \kern -.10em {\sf 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 ${{\sf l} \kern -.10em {\sf R} }^d$ with planes is $O\left(\dbinom{\binom{n}{3}+n}{d(d\!-\!2)}\right)$.

Reference: O. Aichholzer, R. Fabila-Monroy, F. Hurtado, P. Perez-Lantero, A. J. Ruiz-Vargas, J. Urrutia, and B. Vogtenhuber. Cross-sections of line configurations in $R^3$ and $(d\!-\!2)$-flat configurations in $R^d$. Computational Geometry: Theory and Applications, 77:51-61, 2019. Special Issue of CCCG 2014.