LIPIcs, Volume 293
SoCG 2024, June 11-14, 2024, Athens, Greece
Editors: Wolfgang Mulzer and Jeff M. Phillips
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Josh Alman and Yunfeng Guan. Finer-Grained Hardness of Kernel Density Estimation. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 35:1-35:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{alman_et_al:LIPIcs.CCC.2024.35, author = {Alman, Josh and Guan, Yunfeng}, title = {{Finer-Grained Hardness of Kernel Density Estimation}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {35:1--35:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-331-7}, ISSN = {1868-8969}, year = {2024}, volume = {300}, editor = {Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.35}, URN = {urn:nbn:de:0030-drops-204311}, doi = {10.4230/LIPIcs.CCC.2024.35}, annote = {Keywords: Kernel Density Estimation, Fine-Grained Complexity, Schur Polynomials} }
Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)
Patrick Dinklage, Johnnes Fischer, and Nicola Prezza. Top- k Frequent Patterns in Streams and Parameterized-Space LZ Compression. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 9:1-9:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{dinklage_et_al:LIPIcs.SEA.2024.9, author = {Dinklage, Patrick and Fischer, Johnnes and Prezza, Nicola}, title = {{Top- k Frequent Patterns in Streams and Parameterized-Space LZ Compression}}, booktitle = {22nd International Symposium on Experimental Algorithms (SEA 2024)}, pages = {9:1--9: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.9}, URN = {urn:nbn:de:0030-drops-203748}, doi = {10.4230/LIPIcs.SEA.2024.9}, annote = {Keywords: compression, streaming, heavy hitters, algorithm engineering} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Boris Klemz and Marie Diana Sieper. Constrained Level Planarity Is FPT with Respect to the Vertex Cover Number. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 99:1-99:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{klemz_et_al:LIPIcs.ICALP.2024.99, author = {Klemz, Boris and Sieper, Marie Diana}, title = {{Constrained Level Planarity Is FPT with Respect to the Vertex Cover Number}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {99:1--99:17}, 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.99}, URN = {urn:nbn:de:0030-drops-202428}, doi = {10.4230/LIPIcs.ICALP.2024.99}, annote = {Keywords: Parameterized Complexity, Graph Drawing, Planar Poset Diagram, Level Planarity, Constrained Level Planarity, Vertex Cover, FPT, Computational Geometry} }
Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)
40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 1-1412, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@Proceedings{mulzer_et_al:LIPIcs.SoCG.2024, title = {{LIPIcs, Volume 293, SoCG 2024, Complete Volume}}, booktitle = {40th International Symposium on Computational Geometry (SoCG 2024)}, pages = {1--1412}, 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}, URN = {urn:nbn:de:0030-drops-199441}, doi = {10.4230/LIPIcs.SoCG.2024}, annote = {Keywords: LIPIcs, Volume 293, SoCG 2024, Complete Volume} }
Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)
40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 0:i-0:xxii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{mulzer_et_al:LIPIcs.SoCG.2024.0, author = {Mulzer, Wolfgang and Phillips, Jeff M.}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {40th International Symposium on Computational Geometry (SoCG 2024)}, pages = {0:i--0:xxii}, 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.0}, URN = {urn:nbn:de:0030-drops-199457}, doi = {10.4230/LIPIcs.SoCG.2024.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)
Zachary Abel, Hugo A. Akitaya, Scott Duke Kominers, Matias Korman, and Frederick Stock. A Universal In-Place Reconfiguration Algorithm for Sliding Cube-Shaped Robots in a Quadratic Number of Moves. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 1:1-1:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{abel_et_al:LIPIcs.SoCG.2024.1, author = {Abel, Zachary and A. Akitaya, Hugo and Kominers, Scott Duke and Korman, Matias and Stock, Frederick}, title = {{A Universal In-Place Reconfiguration Algorithm for Sliding Cube-Shaped Robots in a Quadratic Number of Moves}}, booktitle = {40th International Symposium on Computational Geometry (SoCG 2024)}, pages = {1:1--1:14}, 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.1}, URN = {urn:nbn:de:0030-drops-199468}, doi = {10.4230/LIPIcs.SoCG.2024.1}, annote = {Keywords: modular reconfigurable robots, sliding cube model, reconfiguration} }
Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)
Mikkel Abrahamsen, Sarita de Berg, Lucas Meijer, André Nusser, and Leonidas Theocharous. Clustering with Few Disks to Minimize the Sum of Radii. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 2:1-2:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{abrahamsen_et_al:LIPIcs.SoCG.2024.2, author = {Abrahamsen, Mikkel and de Berg, Sarita and Meijer, Lucas and Nusser, Andr\'{e} and Theocharous, Leonidas}, title = {{Clustering with Few Disks to Minimize the Sum of Radii}}, booktitle = {40th International Symposium on Computational Geometry (SoCG 2024)}, pages = {2:1--2: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.2}, URN = {urn:nbn:de:0030-drops-199472}, doi = {10.4230/LIPIcs.SoCG.2024.2}, annote = {Keywords: geometric clustering, minimize sum of radii, covering points with disks} }
Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)
Eyal Ackerman, Gábor Damásdi, Balázs Keszegh, Rom Pinchasi, and Rebeka Raffay. On the Number of Digons in Arrangements of Pairwise Intersecting Circles. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 3:1-3:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{ackerman_et_al:LIPIcs.SoCG.2024.3, author = {Ackerman, Eyal and Dam\'{a}sdi, G\'{a}bor and Keszegh, Bal\'{a}zs and Pinchasi, Rom and Raffay, Rebeka}, title = {{On the Number of Digons in Arrangements of Pairwise Intersecting Circles}}, booktitle = {40th International Symposium on Computational Geometry (SoCG 2024)}, pages = {3:1--3:14}, 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.3}, URN = {urn:nbn:de:0030-drops-199480}, doi = {10.4230/LIPIcs.SoCG.2024.3}, annote = {Keywords: Arrangement of pseudocircles, Counting touchings, Counting digons, Gr\"{u}nbaum’s conjecture} }
Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)
Pankaj K. Agarwal, Esther Ezra, and Micha Sharir. Semi-Algebraic Off-Line Range Searching and Biclique Partitions in the Plane. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{agarwal_et_al:LIPIcs.SoCG.2024.4, author = {Agarwal, Pankaj K. and Ezra, Esther and Sharir, Micha}, title = {{Semi-Algebraic Off-Line Range Searching and Biclique Partitions in the Plane}}, booktitle = {40th International Symposium on Computational Geometry (SoCG 2024)}, pages = {4:1--4: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.4}, URN = {urn:nbn:de:0030-drops-199497}, doi = {10.4230/LIPIcs.SoCG.2024.4}, annote = {Keywords: Range-searching, semi-algebraic sets, pseudo-lines, duality, geometric cuttings} }
Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)
Manasseh Ahmed, Tsun-Ming Cheung, Hamed Hatami, and Kusha Sareen. Communication Complexity and Discrepancy of Halfplanes. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 5:1-5:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{ahmed_et_al:LIPIcs.SoCG.2024.5, author = {Ahmed, Manasseh and Cheung, Tsun-Ming and Hatami, Hamed and Sareen, Kusha}, title = {{Communication Complexity and Discrepancy of Halfplanes}}, booktitle = {40th International Symposium on Computational Geometry (SoCG 2024)}, pages = {5:1--5:17}, 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.5}, URN = {urn:nbn:de:0030-drops-199504}, doi = {10.4230/LIPIcs.SoCG.2024.5}, annote = {Keywords: Randomized communication complexity, Discrepancy theory, factorization norm} }
Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)
Ángel Javier Alonso, Michael Kerber, and Primoz Skraba. Probabilistic Analysis of Multiparameter Persistence Decompositions into Intervals. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{alonso_et_al:LIPIcs.SoCG.2024.6, author = {Alonso, \'{A}ngel Javier and Kerber, Michael and Skraba, Primoz}, title = {{Probabilistic Analysis of Multiparameter Persistence Decompositions into Intervals}}, booktitle = {40th International Symposium on Computational Geometry (SoCG 2024)}, pages = {6:1--6:19}, 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.6}, URN = {urn:nbn:de:0030-drops-199510}, doi = {10.4230/LIPIcs.SoCG.2024.6}, annote = {Keywords: Topological Data Analysis, Multi-Parameter Persistence, Decomposition of persistence modules, Poisson point processes} }
Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)
Shinwoo An and Eunjin Oh. ETH-Tight Algorithm for Cycle Packing on Unit Disk Graphs. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{an_et_al:LIPIcs.SoCG.2024.7, author = {An, Shinwoo and Oh, Eunjin}, title = {{ETH-Tight Algorithm for Cycle Packing on Unit Disk Graphs}}, booktitle = {40th International Symposium on Computational Geometry (SoCG 2024)}, pages = {7:1--7: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.7}, URN = {urn:nbn:de:0030-drops-199522}, doi = {10.4230/LIPIcs.SoCG.2024.7}, annote = {Keywords: Unit disk graphs, cycle packing, tree decomposition, parameterized algorithm} }
Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)
Boris Aronov, Abdul Basit, Indu Ramesh, Gianluca Tasinato, and Uli Wagner. Eight-Partitioning Points in 3D, and Efficiently Too. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 8:1-8:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{aronov_et_al:LIPIcs.SoCG.2024.8, author = {Aronov, Boris and Basit, Abdul and Ramesh, Indu and Tasinato, Gianluca and Wagner, Uli}, title = {{Eight-Partitioning Points in 3D, and Efficiently Too}}, booktitle = {40th International Symposium on Computational Geometry (SoCG 2024)}, pages = {8:1--8: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.8}, URN = {urn:nbn:de:0030-drops-199538}, doi = {10.4230/LIPIcs.SoCG.2024.8}, annote = {Keywords: Mass partitions, partitions of points in three dimensions, Borsuk-Ulam Theorem, Ham-Sandwich Theorem} }
Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)
Boris Aronov, Mark de Berg, and Leonidas Theocharous. A Clique-Based Separator for Intersection Graphs of Geodesic Disks in ℝ². In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 9:1-9:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{aronov_et_al:LIPIcs.SoCG.2024.9, author = {Aronov, Boris and de Berg, Mark and Theocharous, Leonidas}, title = {{A Clique-Based Separator for Intersection Graphs of Geodesic Disks in \mathbb{R}²}}, booktitle = {40th International Symposium on Computational Geometry (SoCG 2024)}, pages = {9:1--9: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.9}, URN = {urn:nbn:de:0030-drops-199540}, doi = {10.4230/LIPIcs.SoCG.2024.9}, annote = {Keywords: Computational geometry, intersection graphs, separator theorems} }