An eight-partition of a finite set of points (respectively, of a continuous mass distribution) in <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\mathbb {R}^3$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mrow> <mi mathvariant="double-struck">R</mi> </mrow> <mn>3</mn> </msup> </math></EquationSource> </InlineEquation> 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 <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\mathbb {R}^3$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mrow> <mi mathvariant="double-struck">R</mi> </mrow> <mn>3</mn> </msup> </math></EquationSource> </InlineEquation> 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 <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\mathbb {R}^3$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mrow> <mi mathvariant="double-struck">R</mi> </mrow> <mn>3</mn> </msup> </math></EquationSource> </InlineEquation> 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 <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\mathbb {R}^3$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mrow> <mi mathvariant="double-struck">R</mi> </mrow> <mn>3</mn> </msup> </math></EquationSource> </InlineEquation> (with prescribed normal direction of one of the planes) in time <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$O (n^{7/3})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mrow> <mn>7</mn> <mo stretchy="false">/</mo> <mn>3</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>. A preliminary version of this work appeared in SoCG’24 (Aronov et al., 40th International Symposium on Computational Geometry, 2024).

Eight-Partitioning Points in 3D, and Efficiently Too

期刊论文
出版模式：

开放获取
发表日期：

2025年6月12日

查看全文

Boris Aronov,
Abdul Basit,
Indu Ramesh,
Gianluca Tasinato,
Uli Wagner

摘要

An eight-partition of a finite set of points (respectively, of a continuous mass distribution) in $\mathbb {R}^3$ $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$ $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$ $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$ $R^{3}$ (with prescribed normal direction of one of the planes) in time $O (n^{7/3})$ $O (n^{7 / 3})$ . A preliminary version of this work appeared in SoCG’24 (Aronov et al., 40th International Symposium on Computational Geometry, 2024).