Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
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.
Hoài-Minh Nguyên, Jean Louis-Alexandre Fornerod
Simon François Dumas Primbault