LIPIcs, Volume 189
SoCG 2021, June 7-11, 2021, Buffalo, NY, USA (Virtual Conference)
Editors: Kevin Buchin and Éric Colin de Verdière
Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)
Ambar Pal, Rajiv Raman, Saurabh Ray, and Karamjeet Singh. A Fast Algorithm for Computing a Planar Support for Non-Piercing Rectangles. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 53:1-53:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{pal_et_al:LIPIcs.ISAAC.2024.53, author = {Pal, Ambar and Raman, Rajiv and Ray, Saurabh and Singh, Karamjeet}, title = {{A Fast Algorithm for Computing a Planar Support for Non-Piercing Rectangles}}, booktitle = {35th International Symposium on Algorithms and Computation (ISAAC 2024)}, pages = {53:1--53:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-354-6}, ISSN = {1868-8969}, year = {2024}, volume = {322}, editor = {Mestre, Juli\'{a}n and Wirth, Anthony}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.53}, URN = {urn:nbn:de:0030-drops-221819}, doi = {10.4230/LIPIcs.ISAAC.2024.53}, annote = {Keywords: Algorithms, Hypergraphs, Computational Geometry, Visualization} }
Kevin Buchin, Maike Buchin, Joachim Gudmundsson, Lukas Plätz, Lea Thiel, Sampson Wong. L-Budget Clustering (SWAT 24) (Software). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@misc{dagstuhl-artifact-22471, title = {{L-Budget Clustering (SWAT 24)}}, author = {Buchin, Kevin and Buchin, Maike and Gudmundsson, Joachim and Pl\"{a}tz, Lukas and Thiel, Lea and Wong, Sampson}, note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:c28806ab33cb4a564e1d492efd322b1dc32f7245;origin=https://github.com/NathenMat/SWAT24;visit=swh:1:snp:a052784ff6c68e081ad8aefeaedc032aef15e906;anchor=swh:1:rev:1d5a24b78bbc02b2b3c1e30bce4378db47c66101}{\texttt{swh:1:dir:c28806ab33cb4a564e1d492efd322b1dc32f7245}} (visited on 2024-11-28)}, url = {https://github.com/NathenMat/SWAT24}, doi = {10.4230/artifacts.22471}, }
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 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 293, 40th International Symposium on Computational Geometry (SoCG 2024)
Alkan Atak, Kevin Buchin, Mart Hagedoorn, Jona Heinrichs, Karsten Hogreve, Guangping Li, and Patrick Pawelczyk. Computing Maximum Polygonal Packings in Convex Polygons Using Best-Fit, Genetic Algorithms and ILPs (CG Challenge). In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 83:1-83:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{atak_et_al:LIPIcs.SoCG.2024.83, author = {Atak, Alkan and Buchin, Kevin and Hagedoorn, Mart and Heinrichs, Jona and Hogreve, Karsten and Li, Guangping and Pawelczyk, Patrick}, title = {{Computing Maximum Polygonal Packings in Convex Polygons Using Best-Fit, Genetic Algorithms and ILPs}}, booktitle = {40th International Symposium on Computational Geometry (SoCG 2024)}, pages = {83:1--83:9}, 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.83}, URN = {urn:nbn:de:0030-drops-200283}, doi = {10.4230/LIPIcs.SoCG.2024.83}, annote = {Keywords: Polygon Packing, Nesting Problem, Genetic Algorithm, Integer Linear Programming} }
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)
Joachim Gudmundsson, Zijin Huang, André van Renssen, and Sampson Wong. Computing a Subtrajectory Cluster from c-Packed Trajectories. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{gudmundsson_et_al:LIPIcs.ISAAC.2023.34, author = {Gudmundsson, Joachim and Huang, Zijin and van Renssen, Andr\'{e} and Wong, Sampson}, title = {{Computing a Subtrajectory Cluster from c-Packed Trajectories}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {34:1--34:15}, 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.34}, URN = {urn:nbn:de:0030-drops-193364}, doi = {10.4230/LIPIcs.ISAAC.2023.34}, annote = {Keywords: Subtrajectory cluster, c-packed trajectories, Computational geometry} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Kevin Buchin, Joachim Gudmundsson, Antonia Kalb, Aleksandr Popov, Carolin Rehs, André van Renssen, and Sampson Wong. Oriented Spanners. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 26:1-26:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{buchin_et_al:LIPIcs.ESA.2023.26, author = {Buchin, Kevin and Gudmundsson, Joachim and Kalb, Antonia and Popov, Aleksandr and Rehs, Carolin and van Renssen, Andr\'{e} and Wong, Sampson}, title = {{Oriented Spanners}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {26:1--26:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.26}, URN = {urn:nbn:de:0030-drops-186796}, doi = {10.4230/LIPIcs.ESA.2023.26}, annote = {Keywords: computational geometry, spanner, oriented graph, greedy triangulation} }
Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
Kevin Buchin, Bram Custers, Ivor van der Hoog, Maarten Löffler, Aleksandr Popov, Marcel Roeloffzen, and Frank Staals. Segment Visibility Counting Queries in Polygons. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 58:1-58:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{buchin_et_al:LIPIcs.ISAAC.2022.58, author = {Buchin, Kevin and Custers, Bram and van der Hoog, Ivor and L\"{o}ffler, Maarten and Popov, Aleksandr and Roeloffzen, Marcel and Staals, Frank}, title = {{Segment Visibility Counting Queries in Polygons}}, booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)}, pages = {58:1--58:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-258-7}, ISSN = {1868-8969}, year = {2022}, volume = {248}, editor = {Bae, Sang Won and Park, Heejin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.58}, URN = {urn:nbn:de:0030-drops-173431}, doi = {10.4230/LIPIcs.ISAAC.2022.58}, annote = {Keywords: Visibility, Data Structure, Polygons, Complexity} }
Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)
Peyman Afshani, Mark de Berg, Kevin Buchin, Jie Gao, Maarten Löffler, Amir Nayyeri, Benjamin Raichel, Rik Sarkar, Haotian Wang, and Hao-Tsung Yang. On Cyclic Solutions to the Min-Max Latency Multi-Robot Patrolling Problem. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 2:1-2:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{afshani_et_al:LIPIcs.SoCG.2022.2, author = {Afshani, Peyman and de Berg, Mark and Buchin, Kevin and Gao, Jie and L\"{o}ffler, Maarten and Nayyeri, Amir and Raichel, Benjamin and Sarkar, Rik and Wang, Haotian and Yang, Hao-Tsung}, title = {{On Cyclic Solutions to the Min-Max Latency Multi-Robot Patrolling Problem}}, booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)}, pages = {2:1--2:14}, 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.2}, URN = {urn:nbn:de:0030-drops-160109}, doi = {10.4230/LIPIcs.SoCG.2022.2}, annote = {Keywords: Approximation, Motion Planning, Scheduling} }
Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)
Bahareh Banyassady, Mark de Berg, Karl Bringmann, Kevin Buchin, Henning Fernau, Dan Halperin, Irina Kostitsyna, Yoshio Okamoto, and Stijn Slot. Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{banyassady_et_al:LIPIcs.SoCG.2022.12, author = {Banyassady, Bahareh and de Berg, Mark and Bringmann, Karl and Buchin, Kevin and Fernau, Henning and Halperin, Dan and Kostitsyna, Irina and Okamoto, Yoshio and Slot, Stijn}, title = {{Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds}}, booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)}, pages = {12:1--12:16}, 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.12}, URN = {urn:nbn:de:0030-drops-160203}, doi = {10.4230/LIPIcs.SoCG.2022.12}, annote = {Keywords: motion planning, computational geometry, simple polygon} }
Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)
Kevin Buchin, André Nusser, and Sampson Wong. Computing Continuous Dynamic Time Warping of Time Series in Polynomial Time. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{buchin_et_al:LIPIcs.SoCG.2022.22, author = {Buchin, Kevin and Nusser, Andr\'{e} and Wong, Sampson}, title = {{Computing Continuous Dynamic Time Warping of Time Series in Polynomial Time}}, booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)}, pages = {22:1--22:16}, 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.22}, URN = {urn:nbn:de:0030-drops-160307}, doi = {10.4230/LIPIcs.SoCG.2022.22}, annote = {Keywords: Computational Geometry, Curve Similarity, Fr\'{e}chet distance, Dynamic Time Warping, Continuous Dynamic Time Warping} }
Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Kevin Buchin, Mart Hagedoorn, Irina Kostitsyna, and Max van Mulken. Dots & Boxes Is PSPACE-Complete. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 25:1-25:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{buchin_et_al:LIPIcs.MFCS.2021.25, author = {Buchin, Kevin and Hagedoorn, Mart and Kostitsyna, Irina and van Mulken, Max}, title = {{Dots \& Boxes Is PSPACE-Complete}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {25:1--25:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-201-3}, ISSN = {1868-8969}, year = {2021}, volume = {202}, editor = {Bonchi, Filippo and Puglisi, Simon J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.25}, URN = {urn:nbn:de:0030-drops-144657}, doi = {10.4230/LIPIcs.MFCS.2021.25}, annote = {Keywords: Dots \& Boxes, PSPACE-complete, combinatorial game} }
Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Kevin Buchin, Maarten Löffler, Aleksandr Popov, and Marcel Roeloffzen. Uncertain Curve Simplification. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 26:1-26:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{buchin_et_al:LIPIcs.MFCS.2021.26, author = {Buchin, Kevin and L\"{o}ffler, Maarten and Popov, Aleksandr and Roeloffzen, Marcel}, title = {{Uncertain Curve Simplification}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {26:1--26:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-201-3}, ISSN = {1868-8969}, year = {2021}, volume = {202}, editor = {Bonchi, Filippo and Puglisi, Simon J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.26}, URN = {urn:nbn:de:0030-drops-144666}, doi = {10.4230/LIPIcs.MFCS.2021.26}, annote = {Keywords: Curves, Uncertainty, Simplification, Fr\'{e}chet Distance, Hausdorff Distance} }
Feedback for Dagstuhl Publishing