Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)
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)
@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-dev.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} }
Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)
Jonas Cleve, Nicolas Grelier, Kristin Knorr, Maarten Löffler, Wolfgang Mulzer, and Daniel Perz. Nearest-Neighbor Decompositions of Drawings. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 21:1-21:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{cleve_et_al:LIPIcs.SWAT.2022.21, author = {Cleve, Jonas and Grelier, Nicolas and Knorr, Kristin and L\"{o}ffler, Maarten and Mulzer, Wolfgang and Perz, Daniel}, title = {{Nearest-Neighbor Decompositions of Drawings}}, booktitle = {18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)}, pages = {21:1--21:16}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.21}, URN = {urn:nbn:de:0030-drops-161812}, doi = {10.4230/LIPIcs.SWAT.2022.21}, annote = {Keywords: nearest-neighbors, decompositions, drawing} }
Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)
Sergio Cabello, Michael Hoffmann, Katharina Klost, Wolfgang Mulzer, and Josef Tkadlec. Long Plane Trees. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 23:1-23:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{cabello_et_al:LIPIcs.SoCG.2022.23, author = {Cabello, Sergio and Hoffmann, Michael and Klost, Katharina and Mulzer, Wolfgang and Tkadlec, Josef}, title = {{Long Plane Trees}}, booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)}, pages = {23:1--23:17}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.23}, URN = {urn:nbn:de:0030-drops-160311}, doi = {10.4230/LIPIcs.SoCG.2022.23}, annote = {Keywords: geometric network design, spanning trees, plane straight-line graphs, approximation algorithms} }
Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)
Haim Kaplan, Alexander Kauer, Katharina Klost, Kristin Knorr, Wolfgang Mulzer, Liam Roditty, and Paul Seiferth. Dynamic Connectivity in Disk Graphs. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 49:1-49:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{kaplan_et_al:LIPIcs.SoCG.2022.49, author = {Kaplan, Haim and Kauer, Alexander and Klost, Katharina and Knorr, Kristin and Mulzer, Wolfgang and Roditty, Liam and Seiferth, Paul}, title = {{Dynamic Connectivity in Disk Graphs}}, booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)}, pages = {49:1--49:17}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.49}, URN = {urn:nbn:de:0030-drops-160572}, doi = {10.4230/LIPIcs.SoCG.2022.49}, annote = {Keywords: Disk Graphs, Connectivity, Lower Envelopes} }
Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Sariel Har-Peled and Timothy Zhou. Improved Approximation Algorithms for Tverberg Partitions. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 51:1-51:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{harpeled_et_al:LIPIcs.ESA.2021.51, author = {Har-Peled, Sariel and Zhou, Timothy}, title = {{Improved Approximation Algorithms for Tverberg Partitions}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {51:1--51:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-204-4}, ISSN = {1868-8969}, year = {2021}, volume = {204}, editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.51}, URN = {urn:nbn:de:0030-drops-146323}, doi = {10.4230/LIPIcs.ESA.2021.51}, annote = {Keywords: Geometric spanners, vertex failures, robustness} }
Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Wolfgang Mulzer and Max Willert. Compact Routing in Unit Disk Graphs. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 16:1-16:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{mulzer_et_al:LIPIcs.ISAAC.2020.16, author = {Mulzer, Wolfgang and Willert, Max}, title = {{Compact Routing in Unit Disk Graphs}}, booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)}, pages = {16:1--16:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-173-3}, ISSN = {1868-8969}, year = {2020}, volume = {181}, editor = {Cao, Yixin and Cheng, Siu-Wing and Li, Minming}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.16}, URN = {urn:nbn:de:0030-drops-133602}, doi = {10.4230/LIPIcs.ISAAC.2020.16}, annote = {Keywords: routing scheme, unit disk graph, separator} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Man-Kwun Chiu, Aruni Choudhary, and Wolfgang Mulzer. Computational Complexity of the α-Ham-Sandwich Problem. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 31:1-31:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{chiu_et_al:LIPIcs.ICALP.2020.31, author = {Chiu, Man-Kwun and Choudhary, Aruni and Mulzer, Wolfgang}, title = {{Computational Complexity of the \alpha-Ham-Sandwich Problem}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {31:1--31:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-138-2}, ISSN = {1868-8969}, year = {2020}, volume = {168}, editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.31}, URN = {urn:nbn:de:0030-drops-124382}, doi = {10.4230/LIPIcs.ICALP.2020.31}, annote = {Keywords: Ham-Sandwich Theorem, Computational Complexity, Continuous Local Search} }
Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)
Aruni Choudhary and Wolfgang Mulzer. No-Dimensional Tverberg Theorems and Algorithms. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 31:1-31:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{choudhary_et_al:LIPIcs.SoCG.2020.31, author = {Choudhary, Aruni and Mulzer, Wolfgang}, title = {{No-Dimensional Tverberg Theorems and Algorithms}}, booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)}, pages = {31:1--31:17}, 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.31}, URN = {urn:nbn:de:0030-drops-121893}, doi = {10.4230/LIPIcs.SoCG.2020.31}, annote = {Keywords: Tverberg’s theorem, Colorful Carath\'{e}odory Theorem, Tensor lifting} }
Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)
Wolfgang Mulzer and Pavel Valtr. Long Alternating Paths Exist. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 57:1-57:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{mulzer_et_al:LIPIcs.SoCG.2020.57, author = {Mulzer, Wolfgang and Valtr, Pavel}, title = {{Long Alternating Paths Exist}}, booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)}, pages = {57:1--57: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.57}, URN = {urn:nbn:de:0030-drops-122152}, doi = {10.4230/LIPIcs.SoCG.2020.57}, annote = {Keywords: Non-crossing path, bichromatic point sets} }
Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Édouard Bonnet, Sergio Cabello, and Wolfgang Mulzer. Maximum Matchings in Geometric Intersection Graphs. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 31:1-31:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{bonnet_et_al:LIPIcs.STACS.2020.31, author = {Bonnet, \'{E}douard and Cabello, Sergio and Mulzer, Wolfgang}, title = {{Maximum Matchings in Geometric Intersection Graphs}}, booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, pages = {31:1--31:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-140-5}, ISSN = {1868-8969}, year = {2020}, volume = {154}, editor = {Paul, Christophe and Bl\"{a}ser, Markus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.31}, URN = {urn:nbn:de:0030-drops-118926}, doi = {10.4230/LIPIcs.STACS.2020.31}, annote = {Keywords: computational geometry, geometric intersection graph, maximum matching, disk graph, unit-disk graph} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Haim Kaplan, Katharina Klost, Wolfgang Mulzer, Liam Roditty, Paul Seiferth, and Micha Sharir. Triangles and Girth in Disk Graphs and Transmission Graphs. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 64:1-64:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{kaplan_et_al:LIPIcs.ESA.2019.64, author = {Kaplan, Haim and Klost, Katharina and Mulzer, Wolfgang and Roditty, Liam and Seiferth, Paul and Sharir, Micha}, title = {{Triangles and Girth in Disk Graphs and Transmission Graphs}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {64:1--64:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-124-5}, ISSN = {1868-8969}, year = {2019}, volume = {144}, editor = {Bender, Michael A. and Svensson, Ola and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.64}, URN = {urn:nbn:de:0030-drops-111859}, doi = {10.4230/LIPIcs.ESA.2019.64}, annote = {Keywords: disk graph, transmission graph, triangle, girth} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Ke Chen, Adrian Dumitrescu, Wolfgang Mulzer, and Csaba D. Tóth. On the Stretch Factor of Polygonal Chains. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 56:1-56:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{chen_et_al:LIPIcs.MFCS.2019.56, author = {Chen, Ke and Dumitrescu, Adrian and Mulzer, Wolfgang and T\'{o}th, Csaba D.}, title = {{On the Stretch Factor of Polygonal Chains}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {56:1--56:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.56}, URN = {urn:nbn:de:0030-drops-110005}, doi = {10.4230/LIPIcs.MFCS.2019.56}, annote = {Keywords: polygonal chain, vertex dilation, Koch curve, recursive construction} }
Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)
Pankaj K. Agarwal, Ravid Cohen, Dan Halperin, and Wolfgang Mulzer. Maintaining the Union of Unit Discs Under Insertions with Near-Optimal Overhead. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{agarwal_et_al:LIPIcs.SoCG.2019.26, author = {Agarwal, Pankaj K. and Cohen, Ravid and Halperin, Dan and Mulzer, Wolfgang}, title = {{Maintaining the Union of Unit Discs Under Insertions with Near-Optimal Overhead}}, booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)}, pages = {26:1--26:15}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.26}, URN = {urn:nbn:de:0030-drops-104307}, doi = {10.4230/LIPIcs.SoCG.2019.26}, annote = {Keywords: lower envelopes, pseudo-lines, unit discs, range search, dynamic algorithms, tentative binary search} }
Published in: OASIcs, Volume 69, 2nd Symposium on Simplicity in Algorithms (SOSA 2019)
Luis Barba and Wolfgang Mulzer. Asymmetric Convex Intersection Testing. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{barba_et_al:OASIcs.SOSA.2019.9, author = {Barba, Luis and Mulzer, Wolfgang}, title = {{Asymmetric Convex Intersection Testing}}, booktitle = {2nd Symposium on Simplicity in Algorithms (SOSA 2019)}, pages = {9:1--9:14}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-099-6}, ISSN = {2190-6807}, year = {2019}, volume = {69}, editor = {Fineman, Jeremy T. and Mitzenmacher, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2019.9}, URN = {urn:nbn:de:0030-drops-100358}, doi = {10.4230/OASIcs.SOSA.2019.9}, annote = {Keywords: polytope intersection, LP-type problem, randomized algorithm} }
Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Pankaj K. Agarwal, Haim Kaplan, Geva Kipper, Wolfgang Mulzer, Günter Rote, Micha Sharir, and Allen Xiao. Approximate Minimum-Weight Matching with Outliers Under Translation. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 26:1-26:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{agarwal_et_al:LIPIcs.ISAAC.2018.26, author = {Agarwal, Pankaj K. and Kaplan, Haim and Kipper, Geva and Mulzer, Wolfgang and Rote, G\"{u}nter and Sharir, Micha and Xiao, Allen}, title = {{Approximate Minimum-Weight Matching with Outliers Under Translation}}, booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)}, pages = {26:1--26:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-094-1}, ISSN = {1868-8969}, year = {2018}, volume = {123}, editor = {Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.26}, URN = {urn:nbn:de:0030-drops-99747}, doi = {10.4230/LIPIcs.ISAAC.2018.26}, annote = {Keywords: Minimum-weight partial matching, Pattern matching, Approximation} }
Feedback for Dagstuhl Publishing