@inproceedings{6daebd97bf6e4d4799bed601fc710946,
title = "Eight-Partitioning Points in 3D, and Efficiently Too",
abstract = "An eight-partition of a finite set of points (respectively, of a continuous mass distribution) in R3 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 R3 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 R3 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 R3 (with prescribed normal direction of one of the planes) in time O∗(n5/2).",
keywords = "Borsuk-Ulam Theorem, Ham-Sandwich Theorem, Mass partitions, partitions of points in three dimensions",
author = "Boris Aronov and Abdul Basit and Indu Ramesh and Gianluca Tasinato and Uli Wagner",
note = "Publisher Copyright: {\textcopyright} Boris Aronov, Abdul Basit, Indu Ramesh, Gianluca Tasinato, and Uli Wagner.; 40th International Symposium on Computational Geometry, SoCG 2024 ; Conference date: 11-06-2024 Through 14-06-2024",
year = "2024",
month = jun,
doi = "10.4230/LIPIcs.SoCG.2024.8",
language = "English (US)",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Wolfgang Mulzer and Phillips, {Jeff M.}",
booktitle = "40th International Symposium on Computational Geometry, SoCG 2024",
}