Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)
David Coudert, Mónika Csikós, Guillaume Ducoffe, and Laurent Viennot. Practical Computation of Graph VC-Dimension. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{coudert_et_al:LIPIcs.SEA.2024.8, author = {Coudert, David and Csik\'{o}s, M\'{o}nika and Ducoffe, Guillaume and Viennot, Laurent}, title = {{Practical Computation of Graph VC-Dimension}}, booktitle = {22nd International Symposium on Experimental Algorithms (SEA 2024)}, pages = {8:1--8:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-325-6}, ISSN = {1868-8969}, year = {2024}, volume = {301}, editor = {Liberti, Leo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.8}, URN = {urn:nbn:de:0030-drops-203731}, doi = {10.4230/LIPIcs.SEA.2024.8}, annote = {Keywords: VC-dimension, graph, algorithm} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Michaela Borzechowski, John Fearnley, Spencer Gordon, Rahul Savani, Patrick Schnider, and Simon Weber. Two Choices Are Enough for P-LCPs, USOs, and Colorful Tangents. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 32:1-32:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{borzechowski_et_al:LIPIcs.ICALP.2024.32, author = {Borzechowski, Michaela and Fearnley, John and Gordon, Spencer and Savani, Rahul and Schnider, Patrick and Weber, Simon}, title = {{Two Choices Are Enough for P-LCPs, USOs, and Colorful Tangents}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {32:1--32:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.32}, URN = {urn:nbn:de:0030-drops-201751}, doi = {10.4230/LIPIcs.ICALP.2024.32}, annote = {Keywords: P-LCP, Unique Sink Orientation, \alpha-Ham Sandwich, search complexity, TFNP, UEOPL} }
Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)
Mathilde Bouvel, Valentin Feray, Xavier Goaoc, and Florent Koechlin. A Canonical Tree Decomposition for Chirotopes. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 23:1-23:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bouvel_et_al:LIPIcs.SoCG.2024.23, author = {Bouvel, Mathilde and Feray, Valentin and Goaoc, Xavier and Koechlin, Florent}, title = {{A Canonical Tree Decomposition for Chirotopes}}, booktitle = {40th International Symposium on Computational Geometry (SoCG 2024)}, pages = {23:1--23:18}, 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.23}, URN = {urn:nbn:de:0030-drops-199680}, doi = {10.4230/LIPIcs.SoCG.2024.23}, annote = {Keywords: Order type, modular decomposition, counting triangulations, mutually avoiding point sets, generating functions, rewriting systems} }
Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Johannes Lengler, Anders Martinsson, Kalina Petrova, Patrick Schnider, Raphael Steiner, Simon Weber, and Emo Welzl. On Connectivity in Random Graph Models with Limited Dependencies. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 30:1-30:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{lengler_et_al:LIPIcs.APPROX/RANDOM.2023.30, author = {Lengler, Johannes and Martinsson, Anders and Petrova, Kalina and Schnider, Patrick and Steiner, Raphael and Weber, Simon and Welzl, Emo}, title = {{On Connectivity in Random Graph Models with Limited Dependencies}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {30:1--30:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-296-9}, ISSN = {1868-8969}, year = {2023}, volume = {275}, editor = {Megow, Nicole and Smith, Adam}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.30}, URN = {urn:nbn:de:0030-drops-188556}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.30}, annote = {Keywords: Random Graphs, Independence, Dependency, Connectivity, Threshold, Probabilistic Method} }
Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)
Jean Cardinal and Micha Sharir. Improved Algebraic Degeneracy Testing. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{cardinal_et_al:LIPIcs.SoCG.2023.22, author = {Cardinal, Jean and Sharir, Micha}, title = {{Improved Algebraic Degeneracy Testing}}, booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)}, pages = {22:1--22:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-273-0}, ISSN = {1868-8969}, year = {2023}, volume = {258}, editor = {Chambers, Erin W. and Gudmundsson, Joachim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.22}, URN = {urn:nbn:de:0030-drops-178723}, doi = {10.4230/LIPIcs.SoCG.2023.22}, annote = {Keywords: Degeneracy testing, k-SUM problem, incidence bounds, Hocroft’s problem, polynomial method, algebraic decision trees} }
Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)
Daniel Rutschmann and Manuel Wettstein. Chains, Koch Chains, and Point Sets with Many Triangulations. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 59:1-59:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{rutschmann_et_al:LIPIcs.SoCG.2022.59, author = {Rutschmann, Daniel and Wettstein, Manuel}, title = {{Chains, Koch Chains, and Point Sets with Many Triangulations}}, booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)}, pages = {59:1--59:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-227-3}, ISSN = {1868-8969}, year = {2022}, volume = {224}, editor = {Goaoc, Xavier and Kerber, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.59}, URN = {urn:nbn:de:0030-drops-160678}, doi = {10.4230/LIPIcs.SoCG.2022.59}, annote = {Keywords: Planar Point Set, Chain, Koch Chain, Triangulation, Maximum Number of Triangulations, Lower Bound} }
Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Patrick Schnider. Enclosing Depth and Other Depth Measures. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 10:1-10:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{schnider:LIPIcs.ISAAC.2021.10, author = {Schnider, Patrick}, title = {{Enclosing Depth and Other Depth Measures}}, booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, pages = {10:1--10:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-214-3}, ISSN = {1868-8969}, year = {2021}, volume = {212}, editor = {Ahn, Hee-Kap and Sadakane, Kunihiko}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.10}, URN = {urn:nbn:de:0030-drops-154431}, doi = {10.4230/LIPIcs.ISAAC.2021.10}, annote = {Keywords: Depth measures, Tukey depth, Tverberg theorem, Combinatorial Geometry} }
Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)
Pankaj K. Agarwal, Hsien-Chih Chang, Kamesh Munagala, Erin Taylor, and Emo Welzl. Clustering Under Perturbation Stability in Near-Linear Time. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{agarwal_et_al:LIPIcs.FSTTCS.2020.8, author = {Agarwal, Pankaj K. and Chang, Hsien-Chih and Munagala, Kamesh and Taylor, Erin and Welzl, Emo}, title = {{Clustering Under Perturbation Stability in Near-Linear Time}}, booktitle = {40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)}, pages = {8:1--8:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-174-0}, ISSN = {1868-8969}, year = {2020}, volume = {182}, editor = {Saxena, Nitin and Simon, Sunil}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.8}, URN = {urn:nbn:de:0030-drops-132492}, doi = {10.4230/LIPIcs.FSTTCS.2020.8}, annote = {Keywords: clustering, stability, local search, dynamic programming, coreset, polyhedral metric, trapezoid decomposition, range query} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
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)
@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} }
Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)
Xavier Goaoc and Emo Welzl. Convex Hulls of Random Order Types. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 49:1-49:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{goaoc_et_al:LIPIcs.SoCG.2020.49, author = {Goaoc, Xavier and Welzl, Emo}, title = {{Convex Hulls of Random Order Types}}, booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)}, pages = {49:1--49:15}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.49}, URN = {urn:nbn:de:0030-drops-122074}, doi = {10.4230/LIPIcs.SoCG.2020.49}, annote = {Keywords: order type, oriented matroid, Sylvester’s Four-Point Problem, random convex hull, projective plane, excluded pattern, Hadwiger’s transversal theorem, hairy ball theorem} }
Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)
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)
@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.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} }
Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)
Radoslav Fulek, Bernd Gärtner, Andrey Kupavskii, Pavel Valtr, and Uli Wagner. The Crossing Tverberg Theorem. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 38:1-38:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{fulek_et_al:LIPIcs.SoCG.2019.38, author = {Fulek, Radoslav and G\"{a}rtner, Bernd and Kupavskii, Andrey and Valtr, Pavel and Wagner, Uli}, title = {{The Crossing Tverberg Theorem}}, booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)}, pages = {38:1--38:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-104-7}, ISSN = {1868-8969}, year = {2019}, volume = {129}, editor = {Barequet, Gill and Wang, Yusu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.38}, URN = {urn:nbn:de:0030-drops-104423}, doi = {10.4230/LIPIcs.SoCG.2019.38}, annote = {Keywords: Discrete geometry, Tverberg theorem, Crossing Tverberg theorem} }
Published in: LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)
Jean Cardinal, Jerri Nummenpalo, and Emo Welzl. Solving and Sampling with Many Solutions: Satisfiability and Other Hard Problems. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 11:1-11:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{cardinal_et_al:LIPIcs.IPEC.2017.11, author = {Cardinal, Jean and Nummenpalo, Jerri and Welzl, Emo}, title = {{Solving and Sampling with Many Solutions: Satisfiability and Other Hard Problems}}, booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)}, pages = {11:1--11:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-051-4}, ISSN = {1868-8969}, year = {2018}, volume = {89}, editor = {Lokshtanov, Daniel and Nishimura, Naomi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.11}, URN = {urn:nbn:de:0030-drops-85459}, doi = {10.4230/LIPIcs.IPEC.2017.11}, annote = {Keywords: Satisfiability, Sampling, Parameterized complexity} }
Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)
Alexander Pilz, Emo Welzl, and Manuel Wettstein. From Crossing-Free Graphs on Wheel Sets to Embracing Simplices and Polytopes with Few Vertices. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 54:1-54:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{pilz_et_al:LIPIcs.SoCG.2017.54, author = {Pilz, Alexander and Welzl, Emo and Wettstein, Manuel}, title = {{From Crossing-Free Graphs on Wheel Sets to Embracing Simplices and Polytopes with Few Vertices}}, booktitle = {33rd International Symposium on Computational Geometry (SoCG 2017)}, pages = {54:1--54:16}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.54}, URN = {urn:nbn:de:0030-drops-72101}, doi = {10.4230/LIPIcs.SoCG.2017.54}, annote = {Keywords: Geometric Graph, Wheel Set, Simplicial Depth, Gale Transform, Polytope} }
Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)
Alexander Pilz and Emo Welzl. Order on Order Types. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 285-299, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{pilz_et_al:LIPIcs.SOCG.2015.285, author = {Pilz, Alexander and Welzl, Emo}, title = {{Order on Order Types}}, booktitle = {31st International Symposium on Computational Geometry (SoCG 2015)}, pages = {285--299}, 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.285}, URN = {urn:nbn:de:0030-drops-51194}, doi = {10.4230/LIPIcs.SOCG.2015.285}, annote = {Keywords: point set, order type, planar graph, crossing-free geometric graph} }