Eight-Partitioning Points in 3D, and Efficiently Too

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

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    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).

    Original languageEnglish (US)
    Title of host publication40th International Symposium on Computational Geometry, SoCG 2024
    EditorsWolfgang Mulzer, Jeff M. Phillips
    PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
    ISBN (Electronic)9783959773164
    DOIs
    StatePublished - Jun 2024
    Event40th International Symposium on Computational Geometry, SoCG 2024 - Athens, Greece
    Duration: Jun 11 2024Jun 14 2024

    Publication series

    NameLeibniz International Proceedings in Informatics, LIPIcs
    Volume293
    ISSN (Print)1868-8969

    Conference

    Conference40th International Symposium on Computational Geometry, SoCG 2024
    Country/TerritoryGreece
    CityAthens
    Period6/11/246/14/24

    Keywords

    • Borsuk-Ulam Theorem
    • Ham-Sandwich Theorem
    • Mass partitions
    • partitions of points in three dimensions

    ASJC Scopus subject areas

    • Software

    Fingerprint

    Dive into the research topics of 'Eight-Partitioning Points in 3D, and Efficiently Too'. Together they form a unique fingerprint.

    Cite this