2026-07-23T20:32:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19953 2024-06-06T06:21:13Z ddc:004 open_access

Eight-Partitioning Points in 3D, and Efficiently Too Aronov, Boris Basit, Abdul Ramesh, Indu Tasinato, Gianluca Wagner, Uli Mass partitions partitions of points in three dimensions Borsuk-Ulam Theorem Ham-Sandwich Theorem An eight-partition of a finite set of points (respectively, of a continuous mass distribution) in ℝ³ 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 ℝ³ 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 ℝ³ 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 ℝ³ (with prescribed normal direction of one of the planes) in time O^*(n^{5/2}). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Boris Aronov and Abdul Basit and Indu Ramesh and Gianluca Tasinato and Uli Wagner 2024 Is Part Of LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2024.8 urn:nbn:de:0030-drops-199538 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.8 eng https://creativecommons.org/licenses/by/4.0/legalcode