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.
|
|
| 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] |
|---|---|
| ISSN: | 01795376 |
| DOI: | 10.1007/s00454-025-00739-0 |
