Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Lotte Blank and Anne Driemel. A Faster Algorithm for the Fréchet Distance in 1D for the Imbalanced Case. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 28:1-28:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{blank_et_al:LIPIcs.ESA.2024.28, author = {Blank, Lotte and Driemel, Anne}, title = {{A Faster Algorithm for the Fr\'{e}chet Distance in 1D for the Imbalanced Case}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {28:1--28:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-338-6}, ISSN = {1868-8969}, year = {2024}, volume = {308}, editor = {Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.28}, URN = {urn:nbn:de:0030-drops-210999}, doi = {10.4230/LIPIcs.ESA.2024.28}, annote = {Keywords: \{Fr\'{e}chet distance\}, distance oracle, data structures, time series} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Kevin Buchin, Maike Buchin, Joachim Gudmundsson, and Sampson Wong. Bicriteria Approximation for Minimum Dilation Graph Augmentation. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 36:1-36:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{buchin_et_al:LIPIcs.ESA.2024.36, author = {Buchin, Kevin and Buchin, Maike and Gudmundsson, Joachim and Wong, Sampson}, title = {{Bicriteria Approximation for Minimum Dilation Graph Augmentation}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {36:1--36:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-338-6}, ISSN = {1868-8969}, year = {2024}, volume = {308}, editor = {Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.36}, URN = {urn:nbn:de:0030-drops-211079}, doi = {10.4230/LIPIcs.ESA.2024.36}, annote = {Keywords: Greedy spanner, Graph augmentation} }
Published in: LIPIcs, Volume 315, 16th International Conference on Spatial Information Theory (COSIT 2024)
Steven van den Broek, Wouter Meulemans, Andreas Reimer, and Bettina Speckmann. Scalable Harmonious Simplification of Isolines. In 16th International Conference on Spatial Information Theory (COSIT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 315, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{vandenbroek_et_al:LIPIcs.COSIT.2024.8, author = {van den Broek, Steven and Meulemans, Wouter and Reimer, Andreas and Speckmann, Bettina}, title = {{Scalable Harmonious Simplification of Isolines}}, booktitle = {16th International Conference on Spatial Information Theory (COSIT 2024)}, pages = {8:1--8:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-330-0}, ISSN = {1868-8969}, year = {2024}, volume = {315}, editor = {Adams, Benjamin and Griffin, Amy L. and Scheider, Simon and McKenzie, Grant}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.COSIT.2024.8}, URN = {urn:nbn:de:0030-drops-208230}, doi = {10.4230/LIPIcs.COSIT.2024.8}, annote = {Keywords: Simplification, isolines, harmony} }
Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
Emanuel Herrendorf, Christian Komusiewicz, Nils Morawietz, and Frank Sommer. On the Complexity of Community-Aware Network Sparsification. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 60:1-60:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{herrendorf_et_al:LIPIcs.MFCS.2024.60, author = {Herrendorf, Emanuel and Komusiewicz, Christian and Morawietz, Nils and Sommer, Frank}, title = {{On the Complexity of Community-Aware Network Sparsification}}, booktitle = {49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)}, pages = {60:1--60:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-335-5}, ISSN = {1868-8969}, year = {2024}, volume = {306}, editor = {Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.60}, URN = {urn:nbn:de:0030-drops-206169}, doi = {10.4230/LIPIcs.MFCS.2024.60}, annote = {Keywords: parameterized complexity, hypergraph support, above guarantee parameterization, exponential-time-hypothesis} }
Published in: Dagstuhl Reports, Volume 14, Issue 2 (2024)
Maike Buchin, Jean Cardinal, Arnaud de Mesmay, Jonathan Spreer, and Alex He. Triangulations in Geometry and Topology (Dagstuhl Seminar 24072). In Dagstuhl Reports, Volume 14, Issue 2, pp. 120-163, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@Article{buchin_et_al:DagRep.14.2.120, author = {Buchin, Maike and Cardinal, Jean and de Mesmay, Arnaud and Spreer, Jonathan and He, Alex}, title = {{Triangulations in Geometry and Topology (Dagstuhl Seminar 24072)}}, pages = {120--163}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2024}, volume = {14}, number = {2}, editor = {Buchin, Maike and Cardinal, Jean and de Mesmay, Arnaud and Spreer, Jonathan and He, Alex}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.14.2.120}, URN = {urn:nbn:de:0030-drops-205017}, doi = {10.4230/DagRep.14.2.120}, annote = {Keywords: computational geometry, geometric topology, triangulations} }
Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)
Nick Krumbholz, Stefan Funke, Peter Schäfer, and Sabine Storandt. Algorithms for Gradual Polyline Simplification. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 19:1-19:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{krumbholz_et_al:LIPIcs.SEA.2024.19, author = {Krumbholz, Nick and Funke, Stefan and Sch\"{a}fer, Peter and Storandt, Sabine}, title = {{Algorithms for Gradual Polyline Simplification}}, booktitle = {22nd International Symposium on Experimental Algorithms (SEA 2024)}, pages = {19:1--19:18}, 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.19}, URN = {urn:nbn:de:0030-drops-203847}, doi = {10.4230/LIPIcs.SEA.2024.19}, annote = {Keywords: Polyline simplification, Progressive simplification, Fr\'{e}chet distance} }
Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)
Kevin Buchin, Maike Buchin, Joachim Gudmundsson, Aleksandr Popov, and Sampson Wong. Map-Matching Queries Under Fréchet Distance on Low-Density Spanners. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 27:1-27:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{buchin_et_al:LIPIcs.SoCG.2024.27, author = {Buchin, Kevin and Buchin, Maike and Gudmundsson, Joachim and Popov, Aleksandr and Wong, Sampson}, title = {{Map-Matching Queries Under Fr\'{e}chet Distance on Low-Density Spanners}}, booktitle = {40th International Symposium on Computational Geometry (SoCG 2024)}, pages = {27:1--27:15}, 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.27}, URN = {urn:nbn:de:0030-drops-199723}, doi = {10.4230/LIPIcs.SoCG.2024.27}, annote = {Keywords: Map Matching, Fr\'{e}chet Distance, Data Structures} }
Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)
Kevin Buchin, Maike Buchin, Joachim Gudmundsson, Lukas Plätz, Lea Thiel, and Sampson Wong. Dynamic L-Budget Clustering of Curves. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 18:1-18:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{buchin_et_al:LIPIcs.SWAT.2024.18, author = {Buchin, Kevin and Buchin, Maike and Gudmundsson, Joachim and Pl\"{a}tz, Lukas and Thiel, Lea and Wong, Sampson}, title = {{Dynamic L-Budget Clustering of Curves}}, booktitle = {19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)}, pages = {18:1--18:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-318-8}, ISSN = {1868-8969}, year = {2024}, volume = {294}, editor = {Bodlaender, Hans L.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.18}, URN = {urn:nbn:de:0030-drops-200588}, doi = {10.4230/LIPIcs.SWAT.2024.18}, annote = {Keywords: clustering, streaming algorithm, polygonal curves, Fr\'{e}chet distance, storage efficiency, simplification, approximation algorithms} }
Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Hugo A. Akitaya, Maike Buchin, Majid Mirzanezhad, Leonie Ryvkin, and Carola Wenk. Realizability of Free Spaces of Curves. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 3:1-3:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{a.akitaya_et_al:LIPIcs.ISAAC.2023.3, author = {A. Akitaya, Hugo and Buchin, Maike and Mirzanezhad, Majid and Ryvkin, Leonie and Wenk, Carola}, title = {{Realizability of Free Spaces of Curves}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {3:1--3:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.3}, URN = {urn:nbn:de:0030-drops-193057}, doi = {10.4230/LIPIcs.ISAAC.2023.3}, annote = {Keywords: Fr\'{e}chet distance, Distance Geometry, free space diagram, inverse problem} }
Published in: LIPIcs, Volume 277, 12th International Conference on Geographic Information Science (GIScience 2023)
Maike Buchin and Lukas Plätz. Anonymous Routing Using Minimum Capacity Clustering (Short Paper). In 12th International Conference on Geographic Information Science (GIScience 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 277, pp. 18:1-18:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{buchin_et_al:LIPIcs.GIScience.2023.18, author = {Buchin, Maike and Pl\"{a}tz, Lukas}, title = {{Anonymous Routing Using Minimum Capacity Clustering}}, booktitle = {12th International Conference on Geographic Information Science (GIScience 2023)}, pages = {18:1--18:6}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-288-4}, ISSN = {1868-8969}, year = {2023}, volume = {277}, editor = {Beecham, Roger and Long, Jed A. and Smith, Dianna and Zhao, Qunshan and Wise, Sarah}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2023.18}, URN = {urn:nbn:de:0030-drops-189131}, doi = {10.4230/LIPIcs.GIScience.2023.18}, annote = {Keywords: Anonymity, approximation Algorithms, directed Networks, minimum capacity Clustering, Privacy} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Maike Buchin, Ivor van der Hoog, Tim Ophelders, Lena Schlipf, Rodrigo I. Silveira, and Frank Staals. Efficient Fréchet Distance Queries for Segments. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 29:1-29:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{buchin_et_al:LIPIcs.ESA.2022.29, author = {Buchin, Maike and van der Hoog, Ivor and Ophelders, Tim and Schlipf, Lena and Silveira, Rodrigo I. and Staals, Frank}, title = {{Efficient Fr\'{e}chet Distance Queries for Segments}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {29:1--29:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-247-1}, ISSN = {1868-8969}, year = {2022}, volume = {244}, editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.29}, URN = {urn:nbn:de:0030-drops-169671}, doi = {10.4230/LIPIcs.ESA.2022.29}, annote = {Keywords: Computational Geometry, Data Structures, Fr\'{e}chet distance} }
Published in: Dagstuhl Reports, Volume 12, Issue 2 (2022)
Maike Buchin, Anna Lubiw, Arnaud de Mesmay, Saul Schleimer, and Florestan Brunck. Computation and Reconfiguration in Low-Dimensional Topological Spaces (Dagstuhl Seminar 22062). In Dagstuhl Reports, Volume 12, Issue 2, pp. 17-66, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@Article{buchin_et_al:DagRep.12.2.17, author = {Buchin, Maike and Lubiw, Anna and de Mesmay, Arnaud and Schleimer, Saul and Brunck, Florestan}, title = {{Computation and Reconfiguration in Low-Dimensional Topological Spaces (Dagstuhl Seminar 22062)}}, pages = {17--66}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2022}, volume = {12}, number = {2}, editor = {Buchin, Maike and Lubiw, Anna and de Mesmay, Arnaud and Schleimer, Saul and Brunck, Florestan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.12.2.17}, URN = {urn:nbn:de:0030-drops-169305}, doi = {10.4230/DagRep.12.2.17}, annote = {Keywords: Geometric Topology, Computational Geometry, Graph Drawing, Reconfiguration, Dagstuhl Seminar} }
Published in: LIPIcs, Volume 172, 20th International Workshop on Algorithms in Bioinformatics (WABI 2020)
Leonie Selbach, Tobias Kowalski, Klaus Gerwert, Maike Buchin, and Axel Mosig. Shape Decomposition Algorithms for Laser Capture Microdissection. In 20th International Workshop on Algorithms in Bioinformatics (WABI 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 172, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{selbach_et_al:LIPIcs.WABI.2020.13, author = {Selbach, Leonie and Kowalski, Tobias and Gerwert, Klaus and Buchin, Maike and Mosig, Axel}, title = {{Shape Decomposition Algorithms for Laser Capture Microdissection}}, booktitle = {20th International Workshop on Algorithms in Bioinformatics (WABI 2020)}, pages = {13:1--13:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-161-0}, ISSN = {1868-8969}, year = {2020}, volume = {172}, editor = {Kingsford, Carl and Pisanti, Nadia}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2020.13}, URN = {urn:nbn:de:0030-drops-128020}, doi = {10.4230/LIPIcs.WABI.2020.13}, annote = {Keywords: Laser capture microdissection, shape decomposition, skeletonization} }
Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Hugo Alves Akitaya, Maike Buchin, Leonie Ryvkin, and Jérôme Urhausen. The k-Fréchet Distance: How to Walk Your Dog While Teleporting. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 50:1-50:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{alvesakitaya_et_al:LIPIcs.ISAAC.2019.50, author = {Alves Akitaya, Hugo and Buchin, Maike and Ryvkin, Leonie and Urhausen, J\'{e}r\^{o}me}, title = {{The k-Fr\'{e}chet Distance: How to Walk Your Dog While Teleporting}}, booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)}, pages = {50:1--50:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-130-6}, ISSN = {1868-8969}, year = {2019}, volume = {149}, editor = {Lu, Pinyan and Zhang, Guochuan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.50}, URN = {urn:nbn:de:0030-drops-115462}, doi = {10.4230/LIPIcs.ISAAC.2019.50}, annote = {Keywords: Measures, Fr\'{e}chet distance, Hardness, FPT} }
Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Hugo A. Akitaya, Maike Buchin, Bernhard Kilgus, Stef Sijben, and Carola Wenk. Distance Measures for Embedded Graphs. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 55:1-55:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{akitaya_et_al:LIPIcs.ISAAC.2019.55, author = {Akitaya, Hugo A. and Buchin, Maike and Kilgus, Bernhard and Sijben, Stef and Wenk, Carola}, title = {{Distance Measures for Embedded Graphs}}, booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)}, pages = {55:1--55:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-130-6}, ISSN = {1868-8969}, year = {2019}, volume = {149}, editor = {Lu, Pinyan and Zhang, Guochuan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.55}, URN = {urn:nbn:de:0030-drops-115517}, doi = {10.4230/LIPIcs.ISAAC.2019.55}, annote = {Keywords: Fr\'{e}chet distance, graph comparison, embedded graphs} }
Feedback for Dagstuhl Publishing