Eight-Partitioning Points in 3D, and Efficiently Too.
Saved in:
| Title: | Eight-Partitioning Points in 3D, and Efficiently Too. |
|---|---|
| Authors: | Aronov, Boris1 (AUTHOR) boris.aronov@nyu.edu, Basit, Abdul2 (AUTHOR) abdul.basit@monash.edu, Ramesh, Indu1 (AUTHOR) ir914@nyu.edu, Tasinato, Gianluca3 (AUTHOR) gianluca.tasinato@ist.ac.at, Wagner, Uli3 (AUTHOR) uli@ist.ac.at |
| Source: | Discrete & Computational Geometry. Jun2026, Vol. 75 Issue 4, p1331-1355. 25p. |
| Subjects: | Computational geometry, Time complexity, Probability density function, Geometry, Point cloud |
| Abstract: | An eight-partition of a finite set of points (respectively, of a continuous mass distribution) in R 3 consists of three planes that divide the space into 8 octants, such that each open octant contains at most 1/8 of the points (respectively, of the mass). In 1966, Hadwiger showed that any mass distribution in R 3 admits an eight-partition; moreover, one can prescribe the normal direction of one of the three planes. The analogous result for finite point sets follows by a standard limit argument. We prove the following variant of this result: any mass distribution (or point set) in R 3 admits an eight-partition for which the intersection of two of the planes is a line with a prescribed direction. Moreover, we present an efficient algorithm for calculating an eight-partition of a set of n points in R 3 (with prescribed normal direction of one of the planes) in time O (n 7 / 3) . A preliminary version of this work appeared in SoCG'24 (Aronov et al., 40th International Symposium on Computational Geometry, 2024). [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: 194162868 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Eight-Partitioning Points in 3D, and Efficiently Too. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Aronov%2C+Boris%22">Aronov, Boris</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> boris.aronov@nyu.edu</i><br /><searchLink fieldCode="AR" term="%22Basit%2C+Abdul%22">Basit, Abdul</searchLink><relatesTo>2</relatesTo> (AUTHOR)<i> abdul.basit@monash.edu</i><br /><searchLink fieldCode="AR" term="%22Ramesh%2C+Indu%22">Ramesh, Indu</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> ir914@nyu.edu</i><br /><searchLink fieldCode="AR" term="%22Tasinato%2C+Gianluca%22">Tasinato, Gianluca</searchLink><relatesTo>3</relatesTo> (AUTHOR)<i> gianluca.tasinato@ist.ac.at</i><br /><searchLink fieldCode="AR" term="%22Wagner%2C+Uli%22">Wagner, Uli</searchLink><relatesTo>3</relatesTo> (AUTHOR)<i> uli@ist.ac.at</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Discrete+%26+Computational+Geometry%22">Discrete & Computational Geometry</searchLink>. Jun2026, Vol. 75 Issue 4, p1331-1355. 25p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Computational+geometry%22">Computational geometry</searchLink><br /><searchLink fieldCode="DE" term="%22Time+complexity%22">Time complexity</searchLink><br /><searchLink fieldCode="DE" term="%22Probability+density+function%22">Probability density function</searchLink><br /><searchLink fieldCode="DE" term="%22Geometry%22">Geometry</searchLink><br /><searchLink fieldCode="DE" term="%22Point+cloud%22">Point cloud</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: An eight-partition of a finite set of points (respectively, of a continuous mass distribution) in R 3 consists of three planes that divide the space into 8 octants, such that each open octant contains at most 1/8 of the points (respectively, of the mass). In 1966, Hadwiger showed that any mass distribution in R 3 admits an eight-partition; moreover, one can prescribe the normal direction of one of the three planes. The analogous result for finite point sets follows by a standard limit argument. We prove the following variant of this result: any mass distribution (or point set) in R 3 admits an eight-partition for which the intersection of two of the planes is a line with a prescribed direction. Moreover, we present an efficient algorithm for calculating an eight-partition of a set of n points in R 3 (with prescribed normal direction of one of the planes) in time O (n 7 / 3) . A preliminary version of this work appeared in SoCG'24 (Aronov et al., 40th International Symposium on Computational Geometry, 2024). [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=194162868 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1007/s00454-025-00739-0 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 25 StartPage: 1331 Subjects: – SubjectFull: Computational geometry Type: general – SubjectFull: Time complexity Type: general – SubjectFull: Probability density function Type: general – SubjectFull: Geometry Type: general – SubjectFull: Point cloud Type: general Titles: – TitleFull: Eight-Partitioning Points in 3D, and Efficiently Too. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Aronov, Boris – PersonEntity: Name: NameFull: Basit, Abdul – PersonEntity: Name: NameFull: Ramesh, Indu – PersonEntity: Name: NameFull: Tasinato, Gianluca – PersonEntity: Name: NameFull: Wagner, Uli IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 06 Text: Jun2026 Type: published Y: 2026 Identifiers: – Type: issn-print Value: 01795376 Numbering: – Type: volume Value: 75 – Type: issue Value: 4 Titles: – TitleFull: Discrete & Computational Geometry Type: main |
| ResultId | 1 |
