Intersection Searching amid Tetrahedra in Four Dimensions.
Saved in:
| Title: | Intersection Searching amid Tetrahedra in Four Dimensions. |
|---|---|
| Authors: | Ezra, Esther1 (AUTHOR) ezraest@cs.biu.ac.il, Sharir, Micha2 (AUTHOR) michas@tauex.tau.ac.il |
| Source: | Discrete & Computational Geometry. Mar2025, Vol. 73 Issue 2, p327-369. 43p. |
| Subjects: | Semialgebraic sets, Data structures, Computational geometry, Tetrahedra, Polyhedra |
| Abstract: | We develop data structures for intersection queries in four dimensions that involve segments, triangles and tetrahedra. Specifically, we study three main problems: (i) Preprocess a set of n tetrahedra in R 4 into a data structure for answering segment-intersection queries amid the given tetrahedra (referred to as segment-tetrahedron intersection queries). (ii) Preprocess a set of n triangles in R 4 into a data structure that supports triangle-intersection queries amid the input triangles (referred to as triangle-triangle intersection queries). (iii) Preprocess a set of n segments in R 4 into a data structure that supports tetrahedron-intersection queries amid the input segments (referred to as tetrahedron-segment intersection queries). In each problem we want either to detect an intersection, or to count or report all intersections. As far as we can tell, these problems have not been previously studied. For problem (i), we first present a "standard" solution which, for any prespecified value n ≤ s ≤ n 6 of a so-called storage parameter s, yields a data structure with O ∗ (s) storage and expected preprocessing, which answers an intersection query in O ∗ (n / s 1 / 6) time (here and in what follows, the O ∗ (·) notation hides subpolynomial factors). For problems (ii) and (iii), using similar arguments, we present a solution that has the same asymptotic performance bounds. We then improve the solution for problem (i), and present a more intricate data structure that uses O ∗ (n 2) storage and expected preprocessing, and answers a segment-tetrahedron intersection query in O ∗ (n 1 / 2) time, improving the O ∗ (n 2 / 3) query time obtained by the standard solution. Using the parametric search technique of Agarwal and Matoušek (SIAM J Comput 22:794–806, 1993), we can obtain data structures with similar performance bounds for the ray-shooting problem amid tetrahedra in R 4 . Unfortunately, so far we do not know how to obtain a similar improvement for problems (ii) and (iii). Our algorithms are based on a primal-dual technique for range searching with semi-algebraic sets, based on recent advances in this area (Agarwal et al. in SIAM J Comput 50:760–787, 2021. Also in Proceedings of Symposium on Computational Geometry (SoCG) 5:1–5:14, 2019. Also in arXiv:1812.10269; Matoušek and Patáková in Discrete Comput Geom 54:22–41, 2015). As this is a result of independent interest, we spell out the details of this technique. We present several applications of our techniques, including continuous collision detection amid moving tetrahedra in 3-space, an output-sensitive algorithm for constructing the arrangement of n tetrahedra in R 4 , and an output-sensitive algorithm for constructing the intersection or union of two or several nonconvex polyhedra in R 4 . [ABSTRACT FROM AUTHOR] |
| Copyright of Discrete & Computational Geometry is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
|
Full text is not displayed to guests.
Login for full access.
|
|
| FullText | Links: – Type: pdflink Text: Availability: 1 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 183080255 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Intersection Searching amid Tetrahedra in Four Dimensions. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Ezra%2C+Esther%22">Ezra, Esther</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> ezraest@cs.biu.ac.il</i><br /><searchLink fieldCode="AR" term="%22Sharir%2C+Micha%22">Sharir, Micha</searchLink><relatesTo>2</relatesTo> (AUTHOR)<i> michas@tauex.tau.ac.il</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Discrete+%26+Computational+Geometry%22">Discrete & Computational Geometry</searchLink>. Mar2025, Vol. 73 Issue 2, p327-369. 43p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Semialgebraic+sets%22">Semialgebraic sets</searchLink><br /><searchLink fieldCode="DE" term="%22Data+structures%22">Data structures</searchLink><br /><searchLink fieldCode="DE" term="%22Computational+geometry%22">Computational geometry</searchLink><br /><searchLink fieldCode="DE" term="%22Tetrahedra%22">Tetrahedra</searchLink><br /><searchLink fieldCode="DE" term="%22Polyhedra%22">Polyhedra</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: We develop data structures for intersection queries in four dimensions that involve segments, triangles and tetrahedra. Specifically, we study three main problems: (i) Preprocess a set of n tetrahedra in R 4 into a data structure for answering segment-intersection queries amid the given tetrahedra (referred to as segment-tetrahedron intersection queries). (ii) Preprocess a set of n triangles in R 4 into a data structure that supports triangle-intersection queries amid the input triangles (referred to as triangle-triangle intersection queries). (iii) Preprocess a set of n segments in R 4 into a data structure that supports tetrahedron-intersection queries amid the input segments (referred to as tetrahedron-segment intersection queries). In each problem we want either to detect an intersection, or to count or report all intersections. As far as we can tell, these problems have not been previously studied. For problem (i), we first present a "standard" solution which, for any prespecified value n ≤ s ≤ n 6 of a so-called storage parameter s, yields a data structure with O ∗ (s) storage and expected preprocessing, which answers an intersection query in O ∗ (n / s 1 / 6) time (here and in what follows, the O ∗ (·) notation hides subpolynomial factors). For problems (ii) and (iii), using similar arguments, we present a solution that has the same asymptotic performance bounds. We then improve the solution for problem (i), and present a more intricate data structure that uses O ∗ (n 2) storage and expected preprocessing, and answers a segment-tetrahedron intersection query in O ∗ (n 1 / 2) time, improving the O ∗ (n 2 / 3) query time obtained by the standard solution. Using the parametric search technique of Agarwal and Matoušek (SIAM J Comput 22:794–806, 1993), we can obtain data structures with similar performance bounds for the ray-shooting problem amid tetrahedra in R 4 . Unfortunately, so far we do not know how to obtain a similar improvement for problems (ii) and (iii). Our algorithms are based on a primal-dual technique for range searching with semi-algebraic sets, based on recent advances in this area (Agarwal et al. in SIAM J Comput 50:760–787, 2021. Also in Proceedings of Symposium on Computational Geometry (SoCG) 5:1–5:14, 2019. Also in arXiv:1812.10269; Matoušek and Patáková in Discrete Comput Geom 54:22–41, 2015). As this is a result of independent interest, we spell out the details of this technique. We present several applications of our techniques, including continuous collision detection amid moving tetrahedra in 3-space, an output-sensitive algorithm for constructing the arrangement of n tetrahedra in R 4 , and an output-sensitive algorithm for constructing the intersection or union of two or several nonconvex polyhedra in R 4 . [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of Discrete & Computational Geometry is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=183080255 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1007/s00454-024-00656-8 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 43 StartPage: 327 Subjects: – SubjectFull: Semialgebraic sets Type: general – SubjectFull: Data structures Type: general – SubjectFull: Computational geometry Type: general – SubjectFull: Tetrahedra Type: general – SubjectFull: Polyhedra Type: general Titles: – TitleFull: Intersection Searching amid Tetrahedra in Four Dimensions. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Ezra, Esther – PersonEntity: Name: NameFull: Sharir, Micha IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 03 Text: Mar2025 Type: published Y: 2025 Identifiers: – Type: issn-print Value: 01795376 Numbering: – Type: volume Value: 73 – Type: issue Value: 2 Titles: – TitleFull: Discrete & Computational Geometry Type: main |
| ResultId | 1 |
