4 Search Results for "Joswig, Michael"


Document
Connectivity of Triangulation Flip Graphs in the Plane (Part II: Bistellar Flips)

Authors: Uli Wagner and Emo Welzl

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)


Abstract
Given a finite point set P in general position in the plane, a full triangulation is a maximal straight-line embedded plane graph on P. A partial triangulation on P is a full triangulation of some subset P' of P containing all extreme points in P. A bistellar flip on a partial triangulation either flips an edge, removes a non-extreme point of degree 3, or adds a point in P ⧵ P' as vertex of degree 3. The bistellar flip graph has all partial triangulations as vertices, and a pair of partial triangulations is adjacent if they can be obtained from one another by a bistellar flip. The goal of this paper is to investigate the structure of this graph, with emphasis on its connectivity. For sets P of n points in general position, we show that the bistellar flip graph is (n-3)-connected, thereby answering, for sets in general position, an open questions raised in a book (by De Loera, Rambau, and Santos) and a survey (by Lee and Santos) on triangulations. This matches the situation for the subfamily of regular triangulations (i.e., partial triangulations obtained by lifting the points and projecting the lower convex hull), where (n-3)-connectivity has been known since the late 1980s through the secondary polytope (Gelfand, Kapranov, Zelevinsky) and Balinski’s Theorem. Our methods also yield the following results (see the full version [Wagner and Welzl, 2020]): (i) The bistellar flip graph can be covered by graphs of polytopes of dimension n-3 (products of secondary polytopes). (ii) A partial triangulation is regular, if it has distance n-3 in the Hasse diagram of the partial order of partial subdivisions from the trivial subdivision. (iii) All partial triangulations are regular iff the trivial subdivision has height n-3 in the partial order of partial subdivisions. (iv) There are arbitrarily large sets P with non-regular partial triangulations, while every proper subset has only regular triangulations, i.e., there are no small certificates for the existence of non-regular partial triangulations (answering a question by F. Santos in the unexpected direction).

Cite as

Uli Wagner and Emo Welzl. Connectivity of Triangulation Flip Graphs in the Plane (Part II: Bistellar Flips). In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 67:1-67:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{wagner_et_al:LIPIcs.SoCG.2020.67,
  author =	{Wagner, Uli and Welzl, Emo},
  title =	{{Connectivity of Triangulation Flip Graphs in the Plane (Part II: Bistellar Flips)}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{67:1--67:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.67},
  URN =		{urn:nbn:de:0030-drops-122259},
  doi =		{10.4230/LIPIcs.SoCG.2020.67},
  annote =	{Keywords: triangulation, flip graph, graph connectivity, associahedron, subdivision, convex decomposition, flippable edge, flip complex, regular triangulation, bistellar flip graph, secondary polytope, polyhedral subdivision}
}
Document
Multimedia Contribution
MatchTheNet - An Educational Game on 3-Dimensional Polytopes (Multimedia Contribution)

Authors: Michael Joswig, Georg Loho, Benjamin Lorenz, and Rico Raber

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)


Abstract
We present an interactive game which challenges a single player to match 3-dimensional polytopes to their planar nets. It is open source, and it runs in standard web browsers.

Cite as

Michael Joswig, Georg Loho, Benjamin Lorenz, and Rico Raber. MatchTheNet - An Educational Game on 3-Dimensional Polytopes (Multimedia Contribution). In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 66:1-66:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{joswig_et_al:LIPIcs.SoCG.2017.66,
  author =	{Joswig, Michael and Loho, Georg and Lorenz, Benjamin and Raber, Rico},
  title =	{{MatchTheNet - An Educational Game on 3-Dimensional Polytopes}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{66:1--66:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.66},
  URN =		{urn:nbn:de:0030-drops-72435},
  doi =		{10.4230/LIPIcs.SoCG.2017.66},
  annote =	{Keywords: three-dimensional convex polytopes, unfoldings}
}
Document
Algorithms and Effectivity in Tropical Mathematics and Beyond (Dagstuhl Seminar 16482)

Authors: Stéphane Gaubert, Dima Grigoriev, Michael Joswig, and Thorsten Theobald

Published in: Dagstuhl Reports, Volume 6, Issue 11 (2017)


Abstract
This report documents the Dagstuhl Seminar on Algorithms and Effectivity in Tropical Mathematics and Beyond, which took place from November 27 -- December 02, 2016. The report contains an executive summary as well as abstracts of the talks which reflect recent progress in the topic of the meeting.

Cite as

Stéphane Gaubert, Dima Grigoriev, Michael Joswig, and Thorsten Theobald. Algorithms and Effectivity in Tropical Mathematics and Beyond (Dagstuhl Seminar 16482). In Dagstuhl Reports, Volume 6, Issue 11, pp. 168-184, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@Article{gaubert_et_al:DagRep.6.11.168,
  author =	{Gaubert, St\'{e}phane and Grigoriev, Dima and Joswig, Michael and Theobald, Thorsten},
  title =	{{Algorithms and Effectivity in Tropical Mathematics and Beyond (Dagstuhl Seminar 16482)}},
  pages =	{168--184},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2017},
  volume =	{6},
  number =	{11},
  editor =	{Gaubert, St\'{e}phane and Grigoriev, Dima and Joswig, Michael and Theobald, Thorsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.6.11.168},
  URN =		{urn:nbn:de:0030-drops-71073},
  doi =		{10.4230/DagRep.6.11.168},
  annote =	{Keywords: Algorithms in tropical mathematics, complexity, effective bounds, optimization, zero-sum games}
}
Document
Integration of Algebra and Geometry Software Systems (Dagstuhl Seminar 01421)

Authors: Michael Joswig and Nobuki Takayama

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)


Abstract

Cite as

Michael Joswig and Nobuki Takayama. Integration of Algebra and Geometry Software Systems (Dagstuhl Seminar 01421). Dagstuhl Seminar Report 323, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2002)


Copy BibTex To Clipboard

@TechReport{joswig_et_al:DagSemRep.323,
  author =	{Joswig, Michael and Takayama, Nobuki},
  title =	{{Integration of Algebra and Geometry Software Systems (Dagstuhl Seminar 01421)}},
  pages =	{1--22},
  ISSN =	{1619-0203},
  year =	{2002},
  type = 	{Dagstuhl Seminar Report},
  number =	{323},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.323},
  URN =		{urn:nbn:de:0030-drops-152070},
  doi =		{10.4230/DagSemRep.323},
}
  • Refine by Author
  • 3 Joswig, Michael
  • 1 Gaubert, Stéphane
  • 1 Grigoriev, Dima
  • 1 Loho, Georg
  • 1 Lorenz, Benjamin
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Computational geometry

  • Refine by Keyword
  • 1 Algorithms in tropical mathematics
  • 1 associahedron
  • 1 bistellar flip graph
  • 1 complexity
  • 1 convex decomposition
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 2 2017
  • 1 2002
  • 1 2020

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