Search Results

Documents authored by Bertschinger, Daniel

Document
DOI: 10.4230/LIPIcs.SWAT.2022.16
Well-Separation and Hyperplane Transversals in High Dimensions

Authors: Helena Bergold, Daniel Bertschinger, Nicolas Grelier, Wolfgang Mulzer, and Patrick Schnider

Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)

Abstract
A family of k point sets in d dimensions is well-separated if the convex hulls of any two disjoint subfamilies can be separated by a hyperplane. Well-separation is a strong assumption that allows us to conclude that certain kinds of generalized ham-sandwich cuts for the point sets exist. But how hard is it to check if a given family of high-dimensional point sets has this property? Starting from this question, we study several algorithmic aspects of the existence of transversals and separations in high-dimensions. First, we give an explicit proof that k point sets are well-separated if and only if their convex hulls admit no (k - 2)-transversal, i.e., if there exists no (k - 2)-dimensional flat that intersects the convex hulls of all k sets. It follows that the task of checking well-separation lies in the complexity class coNP. Next, we show that it is NP-hard to decide whether there is a hyperplane-transversal (that is, a (d - 1)-transversal) of a family of d + 1 line segments in ℝ^d, where d is part of the input. As a consequence, it follows that the general problem of testing well-separation is coNP-complete. Furthermore, we show that finding a hyperplane that maximizes the number of intersected sets is NP-hard, but allows for an Ω((log k)/(k log log k))-approximation algorithm that is polynomial in d and k, when each set consists of a single point. When all point sets are finite, we show that checking whether there exists a (k - 2)-transversal is in fact strongly NP-complete. Finally, we take the viewpoint of parametrized complexity, using the dimension d as a parameter: given k convex sets in ℝ^d, checking whether there is a (k-2)-transversal is FPT with respect to d. On the other hand, for k ≥ d+1 finite point sets in ℝ^d, it turns out that checking whether there is a (d-1)-transversal is W[1]-hard with respect to d.
Cite as

Helena Bergold, Daniel Bertschinger, Nicolas Grelier, Wolfgang Mulzer, and Patrick Schnider. Well-Separation and Hyperplane Transversals in High Dimensions. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 16:1-16:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bergold_et_al:LIPIcs.SWAT.2022.16,
  author =	{Bergold, Helena and Bertschinger, Daniel and Grelier, Nicolas and Mulzer, Wolfgang and Schnider, Patrick},
  title =	{{Well-Separation and Hyperplane Transversals in High Dimensions}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{16:1--16:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-236-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{227},
  editor =	{Czumaj, Artur and Xin, Qin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.16},
  URN =		{urn:nbn:de:0030-drops-161766},
  doi =		{10.4230/LIPIcs.SWAT.2022.16},
  annote =	{Keywords: hyperplane transversal, high-dimension, hardness}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2022.17
Lions and Contamination: Monotone Clearings

Authors: Daniel Bertschinger, Meghana M. Reddy, and Enrico Mann

Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)

Abstract
We consider a special variant of a pursuit-evasion game called lions and contamination. In a graph whose vertices are originally contaminated, a set of lions walk around the graph and clear the contamination from every vertex they visit. The contamination, however, simultaneously spreads to any adjacent vertex not occupied by a lion. We study the relationship between different types of clearings of graphs, such as clearings which do not allow recontamination, clearings where at most one lion moves at each time step and clearings where lions are forbidden to be stacked on the same vertex. We answer several questions raised by Adams et al. [H. Adams et al., 2020].
Cite as

Daniel Bertschinger, Meghana M. Reddy, and Enrico Mann. Lions and Contamination: Monotone Clearings. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 17:1-17:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bertschinger_et_al:LIPIcs.SWAT.2022.17,
  author =	{Bertschinger, Daniel and M. Reddy, Meghana and Mann, Enrico},
  title =	{{Lions and Contamination: Monotone Clearings}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{17:1--17:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-236-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{227},
  editor =	{Czumaj, Artur and Xin, Qin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.17},
  URN =		{urn:nbn:de:0030-drops-161778},
  doi =		{10.4230/LIPIcs.SWAT.2022.17},
  annote =	{Keywords: Algorithmic Games, Pursuit-Evasion Games, Graph Contamination, Clearings}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.17
An Optimal Decentralized (Δ + 1)-Coloring Algorithm

Authors: Daniel Bertschinger, Johannes Lengler, Anders Martinsson, Robert Meier, Angelika Steger, Miloš Trujić, and Emo Welzl

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
Consider the following simple coloring algorithm for a graph on n vertices. Each vertex chooses a color from {1, ..., Δ(G) + 1} uniformly at random. While there exists a conflicted vertex choose one such vertex uniformly at random and recolor it with a randomly chosen color. This algorithm was introduced by Bhartia et al. [MOBIHOC'16] for channel selection in WIFI-networks. We show that this algorithm always converges to a proper coloring in expected O(n log Δ) steps, which is optimal and proves a conjecture of Chakrabarty and de Supinski [SOSA'20].
Cite as

Daniel Bertschinger, Johannes Lengler, Anders Martinsson, Robert Meier, Angelika Steger, Miloš Trujić, and Emo Welzl. An Optimal Decentralized (Δ + 1)-Coloring Algorithm. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 17:1-17:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bertschinger_et_al:LIPIcs.ESA.2020.17,
  author =	{Bertschinger, Daniel and Lengler, Johannes and Martinsson, Anders and Meier, Robert and Steger, Angelika and Truji\'{c}, Milo\v{s} and Welzl, Emo},
  title =	{{An Optimal Decentralized (\Delta + 1)-Coloring Algorithm}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{17:1--17:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.17},
  URN =		{urn:nbn:de:0030-drops-128837},
  doi =		{10.4230/LIPIcs.ESA.2020.17},
  annote =	{Keywords: Decentralized Algorithm, Distributed Computing, Graph Coloring, Randomized Algorithms}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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