License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2021.13
URN: urn:nbn:de:0030-drops-154460
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15446/
Go to the corresponding LIPIcs Volume Portal

Schnider, Patrick

The Complexity of Sharing a Pizza

pdf-format:
LIPIcs-ISAAC-2021-13.pdf (0.8 MB)

Abstract

Assume you have a 2-dimensional pizza with 2n ingredients that you want to share with your friend. For this you are allowed to cut the pizza using several straight cuts, and then give every second piece to your friend. You want to do this fairly, that is, your friend and you should each get exactly half of each ingredient. How many cuts do you need?
It was recently shown using topological methods that n cuts always suffice. In this work, we study the computational complexity of finding such n cuts. Our main result is that this problem is PPA-complete when the ingredients are represented as point sets. For this, we give a new proof that for point sets n cuts suffice, which does not use any topological methods.
We further prove several hardness results as well as a higher-dimensional variant for the case where the ingredients are well-separated.

BibTeX - Entry

@InProceedings{schnider:LIPIcs.ISAAC.2021.13,
  author =	{Schnider, Patrick},
  title =	{{The Complexity of Sharing a Pizza}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{13:1--13:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/15446},
  URN =		{urn:nbn:de:0030-drops-154460},
  doi =		{10.4230/LIPIcs.ISAAC.2021.13},
  annote =	{Keywords: pizza sharing, Ham-Sandwich theorem, PPA, computational geometry, computational complexity}
}

Keywords: pizza sharing, Ham-Sandwich theorem, PPA, computational geometry, computational complexity
Collection: 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Issue Date: 2021
Date of publication: 30.11.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI