TY - JOUR
T1 - Cross-sections of line configurations in $R^3$ and $(d-2)$-flat configurations in $R^d$
AU - Aichholzer, Oswin
AU - Fabila-Monroy, Ruy
AU - Hurtado, Ferran
AU - Perez-Lantero, Pablo
AU - Ruiz-Vargas, Andres J.
AU - Urrutia Galicia, Jorge
AU - Vogtenhuber, Birgit
N1 - Special Issue of CCCG 2014
PY - 2019
Y1 - 2019
N2 - We consider sets L={ℓ
1,…,ℓ
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 Π 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 L is O(n
9) when considering all possible planes Π 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 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 R
d with planes is O(((n3)+nd(d−2))).
AB - We consider sets L={ℓ
1,…,ℓ
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 Π 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 L is O(n
9) when considering all possible planes Π 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 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 R
d with planes is O(((n3)+nd(d−2))).
KW - Cross-section
KW - Lines in 3-space
KW - Moving points in the plane
KW - Order type
UR - http://www.scopus.com/inward/record.url?scp=85042560536&partnerID=8YFLogxK
U2 - https://doi.org/10.1016/j.comgeo.2018.02.005
DO - https://doi.org/10.1016/j.comgeo.2018.02.005
M3 - Article
SN - 0925-7721
VL - 77
SP - 51
EP - 61
JO - Computational Geometry
JF - Computational Geometry
ER -