×

Cross-sections of line configurations in \(\mathbb{R}^3\) and (\(d-2\))-flat configurations in \(\mathbb{R}^d\). (English) Zbl 1506.68170

Summary: We consider sets \(\mathcal{L} = \{\ell_1, \ldots, \ell_n \}\) of \(n\) labeled lines in general position in \(\mathbb{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 \(\mathcal{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 \(\mathbb{R}^2\) moving with constant (but possibly different) speeds along straight lines forms at most \(\mathcal{O}(n^3)\) different order types over time. We further generalize the setting from \(\mathbb{R}^3\) to \(\mathbb{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 \(\mathbb{R}^d\) with planes is \(O\left(\left(\begin{matrix} \binom{n}{3} + n \\ d(d - 2)\end{matrix} \right)\right)\).

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
52C30 Planar arrangements of lines and pseudolines (aspects of discrete geometry)
52C35 Arrangements of points, flats, hyperplanes (aspects of discrete geometry)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Agarwal, P. K.; Arge, L.; Erickson, J., Indexing moving points, Special Issue on {PODS} 2000, J. Comput. Syst. Sci., 66, 1, 207-243, (2003) · Zbl 1026.68143
[2] Agarwal, P. K.; Hal-Peled, S., Maintaining approximate extent measures of moving points, (Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, (2001), Society for Industrial and Applied Mathematics), 148-157 · Zbl 1006.68138
[3] Basch, J.; Guibas, L. J.; Hershberger, J., Data structures for mobile data, (Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’97, Philadelphia, PA, USA, (1997), Society for Industrial and Applied Mathematics), 747-756 · Zbl 1321.68213
[4] Chazelle, B.; Edelsbrunner, H.; Guibas, L.; Sharir, M., Lines in space-combinators, algorithms and applications, (Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, STOC ’89, New York, NY, USA, (1989), ACM), 382-393
[5] Goodman, J. E.; Pollack, R., Allowable sequences and order types in discrete and computational geometry, (Pach, János, New Trends in Discrete and Computational Geometry, Algorithms and Combinatorics, vol. 10, (1993), Springer Berlin Heidelberg New York), 103-134 · Zbl 0809.52026
[6] Gudmundsson, J.; van Kreveld, M.; Speckmann, B., Efficient detection of patterns in 2d trajectories of moving points, GeoInformatica, 11, 2, 195-215, (2007)
[7] Guibas, L. J.; Mitchell, J. S.B.; Roos, T., Voronoi diagrams of moving points in the plane, (Schmidt, Gunther; Berghammer, Rudolf, Graph-Theoretic Concepts in Computer Science, LNCS, vol. 570, (1992), Springer Berlin Heidelberg), 113-125 · Zbl 0789.68141
[8] Han, M.; Kanade, T., Reconstruction of a scene with multiple linearly moving objects, Int. J. Comput. Vis., 59, 3, 285-300, (2004)
[9] Hilbert, D.; Cohn-Vossen, S., Geometry and the Imagination, (1958), Chelsea Publishing Company: Chelsea Publishing Company New York · Zbl 0047.38806
[10] Katoh, N.; Tokuyama, T.; Iwano, K., On minimum and maximum spanning trees of linearly moving points, Discrete Comput. Geom., 13, 1, 161-176, (1995) · Zbl 0815.68118
[11] McKenna, M.; O’Rourke, J., Arrangements of lines in 3-space: a data structure with applications, (Proceedings of the Fourth Annual Symposium on Computational Geometry, SCG ’88, New York, NY, USA, (1988), ACM), 371-380
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.