2 Search Results for "Hoffmann, Udo"

Document
DOI: 10.4230/LIPIcs.SoCG.2026.19
Splitting Sandwiches Unevenly via Unique Sink Orientations and Rainbow Arrangements

Authors: Michaela Borzechowski, Sebastian Haslebacher, Hung P. Hoang, Patrick Schnider, and Simon Weber

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
The famous Ham-Sandwich theorem states that any d point sets in ℝ^d can be simultaneously bisected by a single hyperplane. The α-Ham-Sandwich theorem gives a sufficient condition for the existence of biased cuts, i.e., hyperplanes that do not cut off half but some prescribed fraction of each point set. We give two new proofs for this theorem. The first proof is completely combinatorial and highlights a strong connection between the α-Ham-Sandwich theorem and Unique Sink Orientations of grids. The second proof uses point-hyperplane duality and the Poincaré-Miranda theorem and allows us to generalize the result to and beyond oriented matroids. For this we introduce a new concept of rainbow arrangements, generalizing colored pseudo-hyperplane arrangements. Along the way, we also show that the realizability problem for rainbow arrangements is ∃ℝ-complete, which also implies that the realizability problem for grid Unique Sink Orientations is ∃ℝ-complete.
Cite as

Michaela Borzechowski, Sebastian Haslebacher, Hung P. Hoang, Patrick Schnider, and Simon Weber. Splitting Sandwiches Unevenly via Unique Sink Orientations and Rainbow Arrangements. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{borzechowski_et_al:LIPIcs.SoCG.2026.19,
  author =	{Borzechowski, Michaela and Haslebacher, Sebastian and Hoang, Hung P. and Schnider, Patrick and Weber, Simon},
  title =	{{Splitting Sandwiches Unevenly via Unique Sink Orientations and Rainbow Arrangements}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{19:1--19:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.19},
  URN =		{urn:nbn:de:0030-drops-258250},
  doi =		{10.4230/LIPIcs.SoCG.2026.19},
  annote =	{Keywords: \alpha-Ham-Sandwich Theorem, Pseudo-Hyperplanes, Arrangements, Unique Sink Orientations, Oriented Matroids}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.171
Recognition and Complexity of Point Visibility Graphs

Authors: Jean Cardinal and Udo Hoffmann

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract
A point visibility graph is a graph induced by a set of points in the plane, where every vertex corresponds to a point, and two vertices are adjacent whenever the two corresponding points are visible from each other, that is, the open segment between them does not contain any other point of the set. We study the recognition problem for point visibility graphs: given a simple undirected graph, decide whether it is the visibility graph of some point set in the plane. We show that the problem is complete for the existential theory of the reals. Hence the problem is as hard as deciding the existence of a real solution to a system of polynomial inequalities. The proof involves simple substructures forcing collinearities in all realizations of some visibility graphs, which are applied to the algebraic universality constructions of Mnev and Richter-Gebert. This solves a longstanding open question and paves the way for the analysis of other classes of visibility graphs. Furthermore, as a corollary of one of our construction, we show that there exist point visibility graphs that do not admit any geometric realization with points having integer coordinates.
Cite as

Jean Cardinal and Udo Hoffmann. Recognition and Complexity of Point Visibility Graphs. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 171-185, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{cardinal_et_al:LIPIcs.SOCG.2015.171,
  author =	{Cardinal, Jean and Hoffmann, Udo},
  title =	{{Recognition and Complexity of Point Visibility Graphs}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{171--185},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.171},
  URN =		{urn:nbn:de:0030-drops-51390},
  doi =		{10.4230/LIPIcs.SOCG.2015.171},
  annote =	{Keywords: point visibility graphs, recognition, existential theory of the reals}
}
  • Refine by Type
  • 2 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 1 2015

  • Refine by Author
  • 1 Borzechowski, Michaela
  • 1 Cardinal, Jean
  • 1 Haslebacher, Sebastian
  • 1 Hoang, Hung P.
  • 1 Hoffmann, Udo
  • Show More...

  • Refine by Series/Journal
  • 2 LIPIcs

  • Refine by Classification
  • 1 Mathematics of computing → Discrete mathematics
  • 1 Theory of computation → Computational geometry
  • 1 Theory of computation → Problems, reductions and completeness

  • Refine by Keyword
  • 1 Arrangements
  • 1 Oriented Matroids
  • 1 Pseudo-Hyperplanes
  • 1 Unique Sink Orientations
  • 1 existential theory of the reals
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact