Skip to content

Minimising the Sum of Projections of a Finite Set

Research output: Contribution to journalArticle

Original languageEnglish
Pages (from-to)493-511
Number of pages19
JournalDiscrete and Computational Geometry
Volume60
Issue number2
Early online date8 Mar 2018
DOIs
DateAccepted/In press - 18 Feb 2018
DateE-pub ahead of print - 8 Mar 2018
DatePublished (current) - Sep 2018

Abstract

Consider the projections of a finite set (Formula presented.) onto the coordinate hyperplanes; how small can the sum of the sizes of these projections be, given the size of A? In a different form, this problem has been studied earlier in the context of edge-isoperimetric inequalities on graphs, and it can be derived from the known results that there is a linear order on the set of n-tuples with non-negative integer coordinates, such that the sum in question is minimised for the initial segments with respect to this order. We present a new, self-contained and constructive proof, enabling us to obtain a stability result and establish algebraic properties of the smallest possible projection sum. We also solve the problem of minimising the sum of the sizes of the one-dimensional projections.

    Research areas

  • Isoperimetric problem, Loomis–Whitney inequality, Projections

Documents

Documents

  • Full-text PDF (accepted author manuscript)

    Rights statement: This is the author accepted manuscript (AAM). The final published version (version of record) is available online via Springer at https://link.springer.com/article/10.1007%2Fs00454-018-9975-2 . Please refer to any applicable terms of use of the publisher.

    Accepted author manuscript, 215 KB, PDF-document

    Licence: Other

DOI

View research connections

Related faculties, schools or groups