Search Results

Documents authored by Dobbins, Michael Gene

Document
DOI: 10.4230/LIPIcs.SoCG.2024.52
Colorful Intersections and Tverberg Partitions

Authors: Michael Gene Dobbins, Andreas F. Holmsen, and Dohyeon Lee

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

Abstract
The colorful Helly theorem and Tverberg’s theorem are fundamental results in discrete geometry. We prove a theorem which interpolates between the two. In particular, we show the following for any integers d ≥ m ≥ 1 and k a prime power. Suppose F₁, F₂, … , F_m are families of convex sets in ℝ^d, each of size n > (d/m+1)(k-1), such that for any choice C_i ∈ F_i we have ⋂_{i = 1}^m C_i ≠ ∅. Then, one of the families F_i admits a Tverberg k-partition. That is, one of the F_i can be partitioned into k nonempty parts such that the convex hulls of the parts have nonempty intersection. As a corollary, we also obtain a result concerning r-dimensional transversals to families of convex sets in ℝ^d that satisfy the colorful Helly hypothesis, which extends the work of Karasev and Montejano.
Cite as

Michael Gene Dobbins, Andreas F. Holmsen, and Dohyeon Lee. Colorful Intersections and Tverberg Partitions. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 52:1-52:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dobbins_et_al:LIPIcs.SoCG.2024.52,
  author =	{Dobbins, Michael Gene and Holmsen, Andreas F. and Lee, Dohyeon},
  title =	{{Colorful Intersections and Tverberg Partitions}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{52:1--52:13},
  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.52},
  URN =		{urn:nbn:de:0030-drops-199973},
  doi =		{10.4230/LIPIcs.SoCG.2024.52},
  annote =	{Keywords: Tverberg’s theorem, geometric transversals, topological combinatorics, configuration space/test map, discrete Morse theory}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.10
The Number of Holes in the Union of Translates of a Convex Set in Three Dimensions

Authors: Boris Aronov, Otfried Cheong, Michael Gene Dobbins, and Xavier Goaoc

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
We show that the union of translates of a convex body in three dimensional space can have a cubic number holes in the worst case, where a hole in a set is a connected component of its compliment. This refutes a 20-year-old conjecture. As a consequence, we also obtain improved lower bounds on the complexity of motion planning problems and of Voronoi diagrams with convex distance functions.
Cite as

Boris Aronov, Otfried Cheong, Michael Gene Dobbins, and Xavier Goaoc. The Number of Holes in the Union of Translates of a Convex Set in Three Dimensions. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{aronov_et_al:LIPIcs.SoCG.2016.10,
  author =	{Aronov, Boris and Cheong, Otfried and Dobbins, Michael Gene and Goaoc, Xavier},
  title =	{{The Number of Holes in the Union of Translates of a Convex Set in Three Dimensions}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.10},
  URN =		{urn:nbn:de:0030-drops-59024},
  doi =		{10.4230/LIPIcs.SoCG.2016.10},
  annote =	{Keywords: Union complexity, Convex sets, Motion planning}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.599
Realization Spaces of Arrangements of Convex Bodies

Authors: Michael Gene Dobbins, Andreas Holmsen, and Alfredo Hubard

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

Abstract
We introduce combinatorial types of arrangements of convex bodies, extending order types of point sets to arrangements of convex bodies, and study their realization spaces. Our main results witness a trade-off between the combinatorial complexity of the bodies and the topological complexity of their realization space. On one hand, we show that every combinatorial type can be realized by an arrangement of convex bodies and (under mild assumptions) its realization space is contractible. On the other hand, we prove a universality theorem that says that the restriction of the realization space to arrangements of convex polygons with a bounded number of vertices can have the homotopy type of any primary semialgebraic set.
Cite as

Michael Gene Dobbins, Andreas Holmsen, and Alfredo Hubard. Realization Spaces of Arrangements of Convex Bodies. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 599-614, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{dobbins_et_al:LIPIcs.SOCG.2015.599,
  author =	{Dobbins, Michael Gene and Holmsen, Andreas and Hubard, Alfredo},
  title =	{{Realization Spaces of Arrangements of Convex Bodies}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{599--614},
  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.599},
  URN =		{urn:nbn:de:0030-drops-51020},
  doi =		{10.4230/LIPIcs.SOCG.2015.599},
  annote =	{Keywords: Oriented matroids, Convex sets, Realization spaces, Mnev’s universality theorem}
}
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