Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Cross-sections of line configurations in R-3 and (d-2)-flat configurations in R-d
 
research article

Cross-sections of line configurations in R-3 and (d-2)-flat configurations in R-d

Aichholzer, Oswin
•
Fabila-Monroy, Ruy
•
Hurtado, Ferran
Show more
March 1, 2019
Computational Geometry-Theory And Applications

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.

  • Details
  • Metrics
Type
research article
DOI
10.1016/j.comgeo.2018.02.005
Web of Science ID

WOS:000454975800006

Author(s)
Aichholzer, Oswin
Fabila-Monroy, Ruy
Hurtado, Ferran
Perez-Lantero, Pablo
Ruiz-Vargas, Andres J.  
Urrutia, Jorge
Vogtenhuber, Birgit
Date Issued

2019-03-01

Publisher

ELSEVIER SCIENCE BV

Published in
Computational Geometry-Theory And Applications
Volume

77

Start page

51

End page

61

Subjects

Mathematics, Applied

•

Mathematics

•

order type

•

cross-section

•

lines in 3-space

•

moving points in the plane

Note

26th Canadian Conference on Computational Geometry (CCCG), Halifax, CANADA, Aug 11-13, 2014

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DCG  
MATHGEOM  
Available on Infoscience
January 23, 2019
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/153986
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés