Eight-Partitioning Points in 3D, and Efficiently Too
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912377962758144 |
|---|---|
| author | Aronov, Boris Basit, Abdul Ramesh, Indu Tasinato, Gianluca Wagner, Uli |
| author_facet | Aronov, Boris Basit, Abdul Ramesh, Indu Tasinato, Gianluca Wagner, Uli |
| contents | An {\em eight-partition} of a finite set of points (respectively, of a continuous mass distribution) in $\mathbb{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 $\mathbb{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 $\mathbb{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~$\mathbb{R}^3$ (with prescribed normal direction of one of the planes) in time $O^{*}(n^{7/3})$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_02627 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Eight-Partitioning Points in 3D, and Efficiently Too Aronov, Boris Basit, Abdul Ramesh, Indu Tasinato, Gianluca Wagner, Uli Computational Geometry Combinatorics 52-08, 52C45, 52C35, 68Q25 An {\em eight-partition} of a finite set of points (respectively, of a continuous mass distribution) in $\mathbb{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 $\mathbb{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 $\mathbb{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~$\mathbb{R}^3$ (with prescribed normal direction of one of the planes) in time $O^{*}(n^{7/3})$. |
| title | Eight-Partitioning Points in 3D, and Efficiently Too |
| topic | Computational Geometry Combinatorics 52-08, 52C45, 52C35, 68Q25 |
| url | https://arxiv.org/abs/2403.02627 |