Search Results

Documents authored by Tasinato, Gianluca

Document
DOI: 10.4230/LIPIcs.SoCG.2024.8
Eight-Partitioning Points in 3D, and Efficiently Too

Authors: Boris Aronov, Abdul Basit, Indu Ramesh, Gianluca Tasinato, and Uli Wagner

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
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}).
Cite as

Boris Aronov, Abdul Basit, Indu Ramesh, Gianluca Tasinato, and Uli Wagner. Eight-Partitioning Points in 3D, and Efficiently Too. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 8:1-8:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{aronov_et_al:LIPIcs.SoCG.2024.8,
  author =	{Aronov, Boris and Basit, Abdul and Ramesh, Indu and Tasinato, Gianluca and Wagner, Uli},
  title =	{{Eight-Partitioning Points in 3D, and Efficiently Too}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{8:1--8:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.8},
  URN =		{urn:nbn:de:0030-drops-199538},
  doi =		{10.4230/LIPIcs.SoCG.2024.8},
  annote =	{Keywords: Mass partitions, partitions of points in three dimensions, Borsuk-Ulam Theorem, Ham-Sandwich Theorem}
}
Document
DOI: 10.4230/LIPIcs.STACS.2024.34
Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs

Authors: Marek Filakovský, Tamio-Vesa Nakajima, Jakub Opršal, Gianluca Tasinato, and Uli Wagner

Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)

Abstract
A linearly ordered (LO) k-colouring of a hypergraph is a colouring of its vertices with colours 1, … , k such that each edge contains a unique maximal colour. Deciding whether an input hypergraph admits LO k-colouring with a fixed number of colours is NP-complete (and in the special case of graphs, LO colouring coincides with the usual graph colouring). Here, we investigate the complexity of approximating the "linearly ordered chromatic number" of a hypergraph. We prove that the following promise problem is NP-complete: Given a 3-uniform hypergraph, distinguish between the case that it is LO 3-colourable, and the case that it is not even LO 4-colourable. We prove this result by a combination of algebraic, topological, and combinatorial methods, building on and extending a topological approach for studying approximate graph colouring introduced by Krokhin, Opršal, Wrochna, and Živný (2023).
Cite as

Marek Filakovský, Tamio-Vesa Nakajima, Jakub Opršal, Gianluca Tasinato, and Uli Wagner. Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 34:1-34:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{filakovsky_et_al:LIPIcs.STACS.2024.34,
  author =	{Filakovsk\'{y}, Marek and Nakajima, Tamio-Vesa and Opr\v{s}al, Jakub and Tasinato, Gianluca and Wagner, Uli},
  title =	{{Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{34:1--34:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.34},
  URN =		{urn:nbn:de:0030-drops-197445},
  doi =		{10.4230/LIPIcs.STACS.2024.34},
  annote =	{Keywords: constraint satisfaction problem, hypergraph colouring, promise problem, topological methods}
}
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact