Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Argyrios Deligkas, Eduard Eiben, Robert Ganian, Iyad Kanj, and M. S. Ramanujan. Parameterized Algorithms for Coordinated Motion Planning: Minimizing Energy. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 53:1-53:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{deligkas_et_al:LIPIcs.ICALP.2024.53, author = {Deligkas, Argyrios and Eiben, Eduard and Ganian, Robert and Kanj, Iyad and Ramanujan, M. S.}, title = {{Parameterized Algorithms for Coordinated Motion Planning: Minimizing Energy}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {53:1--53: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.53}, URN = {urn:nbn:de:0030-drops-201968}, doi = {10.4230/LIPIcs.ICALP.2024.53}, annote = {Keywords: coordinated motion planning, multi-agent path finding, parameterized complexity} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Itai Boneh, Shay Golan, Shay Mozes, and Oren Weimann. Õptimal Dynamic Time Warping on Run-Length Encoded Strings. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 30:1-30:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{boneh_et_al:LIPIcs.ICALP.2024.30, author = {Boneh, Itai and Golan, Shay and Mozes, Shay and Weimann, Oren}, title = {{\~{O}ptimal Dynamic Time Warping on Run-Length Encoded Strings}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {30:1--30: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.30}, URN = {urn:nbn:de:0030-drops-201730}, doi = {10.4230/LIPIcs.ICALP.2024.30}, annote = {Keywords: Dynamic time warping, Fr\'{e}chet distance, edit distance, run-length encoding} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Adam Karczmarz and Marcin Smulewicz. Fully Dynamic Strongly Connected Components in Planar Digraphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 95:1-95:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{karczmarz_et_al:LIPIcs.ICALP.2024.95, author = {Karczmarz, Adam and Smulewicz, Marcin}, title = {{Fully Dynamic Strongly Connected Components in Planar Digraphs}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {95:1--95:20}, 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.95}, URN = {urn:nbn:de:0030-drops-202388}, doi = {10.4230/LIPIcs.ICALP.2024.95}, annote = {Keywords: dynamic strongly connected components, dynamic strong connectivity, dynamic reachability, planar graphs} }
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 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Haim Kaplan, Matthew J. Katz, Rachel Saban, and Micha Sharir. The Unweighted and Weighted Reverse Shortest Path Problem for Disk Graphs. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 67:1-67:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{kaplan_et_al:LIPIcs.ESA.2023.67, author = {Kaplan, Haim and Katz, Matthew J. and Saban, Rachel and Sharir, Micha}, title = {{The Unweighted and Weighted Reverse Shortest Path Problem for Disk Graphs}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {67:1--67:14}, 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.67}, URN = {urn:nbn:de:0030-drops-187208}, doi = {10.4230/LIPIcs.ESA.2023.67}, annote = {Keywords: Computational geometry, geometric optimization, disk graphs, BFS, Dijkstra’s algorithm, reverse shortest path} }
Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)
Peyman Afshani and Pingan Cheng. Lower Bounds for Intersection Reporting Among Flat Objects. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 3:1-3:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{afshani_et_al:LIPIcs.SoCG.2023.3, author = {Afshani, Peyman and Cheng, Pingan}, title = {{Lower Bounds for Intersection Reporting Among Flat Objects}}, booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)}, pages = {3:1--3: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.3}, URN = {urn:nbn:de:0030-drops-178536}, doi = {10.4230/LIPIcs.SoCG.2023.3}, annote = {Keywords: Computational Geometry, Intersection Searching, Data Structure Lower Bounds} }
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 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
Pankaj K. Agarwal, Matthew J. Katz, and Micha Sharir. On Reverse Shortest Paths in Geometric Proximity Graphs. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 42:1-42:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{agarwal_et_al:LIPIcs.ISAAC.2022.42, author = {Agarwal, Pankaj K. and Katz, Matthew J. and Sharir, Micha}, title = {{On Reverse Shortest Paths in Geometric Proximity Graphs}}, booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)}, pages = {42:1--42:19}, 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.42}, URN = {urn:nbn:de:0030-drops-173277}, doi = {10.4230/LIPIcs.ISAAC.2022.42}, annote = {Keywords: Geometric optimization, proximity graphs, semi-algebraic range searching, reverse shortest path} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Esther Ezra and Micha Sharir. Intersection Searching Amid Tetrahedra in 4-Space and Efficient Continuous Collision Detection. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 51:1-51:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{ezra_et_al:LIPIcs.ESA.2022.51, author = {Ezra, Esther and Sharir, Micha}, title = {{Intersection Searching Amid Tetrahedra in 4-Space and Efficient Continuous Collision Detection}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {51:1--51:17}, 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.51}, URN = {urn:nbn:de:0030-drops-169895}, doi = {10.4230/LIPIcs.ESA.2022.51}, annote = {Keywords: Computational geometry, Ray shooting, Tetrahedra in \{\mathbb{R}\}⁴, Intersection queries in \{\mathbb{R}\}⁴, Polynomial partitioning, Range searching, Semi-algebraic sets, Tradeoff} }
Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)
Pankaj K. Agarwal, Boris Aronov, Esther Ezra, Matthew J. Katz, and Micha Sharir. Intersection Queries for Flat Semi-Algebraic Objects in Three Dimensions and Related Problems. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 4:1-4:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{agarwal_et_al:LIPIcs.SoCG.2022.4, author = {Agarwal, Pankaj K. and Aronov, Boris and Ezra, Esther and Katz, Matthew J. and Sharir, Micha}, title = {{Intersection Queries for Flat Semi-Algebraic Objects in Three Dimensions and Related Problems}}, booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)}, pages = {4:1--4: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.4}, URN = {urn:nbn:de:0030-drops-160126}, doi = {10.4230/LIPIcs.SoCG.2022.4}, annote = {Keywords: Intersection searching, Semi-algebraic range searching, Point-enclosure queries, Ray-shooting queries, Polynomial partitions, Cylindrical algebraic decomposition, Multi-level partition trees, Collision detection} }
Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)
Zuzana Patáková and Micha Sharir. Covering Points by Hyperplanes and Related Problems. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 57:1-57:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{patakova_et_al:LIPIcs.SoCG.2022.57, author = {Pat\'{a}kov\'{a}, Zuzana and Sharir, Micha}, title = {{Covering Points by Hyperplanes and Related Problems}}, booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)}, pages = {57:1--57:7}, 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.57}, URN = {urn:nbn:de:0030-drops-160652}, doi = {10.4230/LIPIcs.SoCG.2022.57}, annote = {Keywords: Rich hyperplanes, Incidences, Covering points by hyperplanes} }
Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Boris Aronov, Mark de Berg, Jean Cardinal, Esther Ezra, John Iacono, and Micha Sharir. Subquadratic Algorithms for Some 3Sum-Hard Geometric Problems in the Algebraic Decision Tree Model. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{aronov_et_al:LIPIcs.ISAAC.2021.3, author = {Aronov, Boris and de Berg, Mark and Cardinal, Jean and Ezra, Esther and Iacono, John and Sharir, Micha}, title = {{Subquadratic Algorithms for Some 3Sum-Hard Geometric Problems in the Algebraic Decision Tree Model}}, booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, pages = {3:1--3: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.3}, URN = {urn:nbn:de:0030-drops-154363}, doi = {10.4230/LIPIcs.ISAAC.2021.3}, annote = {Keywords: Computational geometry, Algebraic decision-tree model, Polynomial partitioning, Primal-dual range searching, Order types, Point location, Hierarchical partitions} }
Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)
Esther Ezra and Micha Sharir. On Ray Shooting for Triangles in 3-Space and Related Problems. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{ezra_et_al:LIPIcs.SoCG.2021.34, author = {Ezra, Esther and Sharir, Micha}, title = {{On Ray Shooting for Triangles in 3-Space and Related Problems}}, booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)}, pages = {34:1--34:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-184-9}, ISSN = {1868-8969}, year = {2021}, volume = {189}, editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.34}, URN = {urn:nbn:de:0030-drops-138332}, doi = {10.4230/LIPIcs.SoCG.2021.34}, annote = {Keywords: Ray shooting, Three dimensions, Polynomial partitioning, Tradeoff} }
Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)
Esther Ezra, Orit E. Raz, Micha Sharir, and Joshua Zahl. On Rich Lenses in Planar Arrangements of Circles and Related Problems. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 35:1-35:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{ezra_et_al:LIPIcs.SoCG.2021.35, author = {Ezra, Esther and Raz, Orit E. and Sharir, Micha and Zahl, Joshua}, title = {{On Rich Lenses in Planar Arrangements of Circles and Related Problems}}, booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)}, pages = {35:1--35:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-184-9}, ISSN = {1868-8969}, year = {2021}, volume = {189}, editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.35}, URN = {urn:nbn:de:0030-drops-138343}, doi = {10.4230/LIPIcs.SoCG.2021.35}, annote = {Keywords: Lenses, Circles, Polynomial partitioning, Incidences} }
Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)
Dan Halperin, Micha Sharir, and Itay Yehuda. Throwing a Sofa Through the Window. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 41:1-41:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{halperin_et_al:LIPIcs.SoCG.2021.41, author = {Halperin, Dan and Sharir, Micha and Yehuda, Itay}, title = {{Throwing a Sofa Through the Window}}, booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)}, pages = {41:1--41:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-184-9}, ISSN = {1868-8969}, year = {2021}, volume = {189}, editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.41}, URN = {urn:nbn:de:0030-drops-138409}, doi = {10.4230/LIPIcs.SoCG.2021.41}, annote = {Keywords: Motion planning, Convex polytopes in 3D} }