Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, and Yoshio Okamoto. Hardness of Finding Combinatorial Shortest Paths on Graph Associahedra. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 82:1-82:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{ito_et_al:LIPIcs.ICALP.2023.82, author = {Ito, Takehiro and Kakimura, Naonori and Kamiyama, Naoyuki and Kobayashi, Yusuke and Maezawa, Shun-ichi and Nozaki, Yuta and Okamoto, Yoshio}, title = {{Hardness of Finding Combinatorial Shortest Paths on Graph Associahedra}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {82:1--82:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.82}, URN = {urn:nbn:de:0030-drops-181344}, doi = {10.4230/LIPIcs.ICALP.2023.82}, annote = {Keywords: Graph associahedra, combinatorial shortest path, NP-hardness, polymatroids} }
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 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Justin Dallant and John Iacono. Conditional Lower Bounds for Dynamic Geometric Measure Problems. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 39:1-39:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{dallant_et_al:LIPIcs.ESA.2022.39, author = {Dallant, Justin and Iacono, John}, title = {{Conditional Lower Bounds for Dynamic Geometric Measure Problems}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {39:1--39: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.39}, URN = {urn:nbn:de:0030-drops-169777}, doi = {10.4230/LIPIcs.ESA.2022.39}, annote = {Keywords: Computational geometry, Fine-grained complexity, Dynamic data structures} }
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 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Jean Cardinal, Justin Dallant, and John Iacono. An Instance-Optimal Algorithm for Bichromatic Rectangular Visibility. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 24:1-24:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{cardinal_et_al:LIPIcs.ESA.2021.24, author = {Cardinal, Jean and Dallant, Justin and Iacono, John}, title = {{An Instance-Optimal Algorithm for Bichromatic Rectangular Visibility}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {24:1--24:14}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.24}, URN = {urn:nbn:de:0030-drops-146057}, doi = {10.4230/LIPIcs.ESA.2021.24}, annote = {Keywords: computational geometry, instance-optimality, colored point sets, empty rectangles, visibility} }
Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Jean Cardinal, John Iacono, and Grigorios Koumoutsos. Worst-Case Efficient Dynamic Geometric Independent Set. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 25:1-25:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{cardinal_et_al:LIPIcs.ESA.2021.25, author = {Cardinal, Jean and Iacono, John and Koumoutsos, Grigorios}, title = {{Worst-Case Efficient Dynamic Geometric Independent Set}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {25:1--25: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.25}, URN = {urn:nbn:de:0030-drops-146061}, doi = {10.4230/LIPIcs.ESA.2021.25}, annote = {Keywords: Maximum independent set, deamortization, approximation} }
Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Boris Aronov and Jean Cardinal. Geometric Pattern Matching Reduces to k-SUM. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 32:1-32:9, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{aronov_et_al:LIPIcs.ISAAC.2020.32, author = {Aronov, Boris and Cardinal, Jean}, title = {{Geometric Pattern Matching Reduces to k-SUM}}, booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)}, pages = {32:1--32:9}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.32}, URN = {urn:nbn:de:0030-drops-133760}, doi = {10.4230/LIPIcs.ISAAC.2020.32}, annote = {Keywords: Geometric pattern matching, k-SUM problem, Linear decision trees} }
Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)
Jean Cardinal and Aurélien Ooms. Sparse Regression via Range Counting. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 20:1-20:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{cardinal_et_al:LIPIcs.SWAT.2020.20, author = {Cardinal, Jean and Ooms, Aur\'{e}lien}, title = {{Sparse Regression via Range Counting}}, booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)}, pages = {20:1--20:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-150-4}, ISSN = {1868-8969}, year = {2020}, volume = {162}, editor = {Albers, Susanne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.20}, URN = {urn:nbn:de:0030-drops-122677}, doi = {10.4230/LIPIcs.SWAT.2020.20}, annote = {Keywords: Sparse Linear Regression, Orthogonal Range Searching, Affine Degeneracy Testing, Nearest Neighbors, Hyperplane Arrangements} }
Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)
Boris Aronov, Esther Ezra, and Micha Sharir. Testing Polynomials for Vanishing on Cartesian Products of Planar Point Sets. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 8:1-8:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{aronov_et_al:LIPIcs.SoCG.2020.8, author = {Aronov, Boris and Ezra, Esther and Sharir, Micha}, title = {{Testing Polynomials for Vanishing on Cartesian Products of Planar Point Sets}}, booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)}, pages = {8:1--8:14}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.8}, URN = {urn:nbn:de:0030-drops-121666}, doi = {10.4230/LIPIcs.SoCG.2020.8}, annote = {Keywords: Algebraic decision tree, Polynomial partition, Collinearity testing, 3SUM-hard problems, Polynomials vanishing on Cartesian products} }
Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)
Ivor van der Hoog, Irina Kostitsyna, Maarten Löffler, and Bettina Speckmann. Preprocessing Ambiguous Imprecise Points. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 42:1-42:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{vanderhoog_et_al:LIPIcs.SoCG.2019.42, author = {van der Hoog, Ivor and Kostitsyna, Irina and L\"{o}ffler, Maarten and Speckmann, Bettina}, title = {{Preprocessing Ambiguous Imprecise Points}}, booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)}, pages = {42:1--42:16}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.42}, URN = {urn:nbn:de:0030-drops-104460}, doi = {10.4230/LIPIcs.SoCG.2019.42}, annote = {Keywords: preprocessing, imprecise points, entropy, sorting, proximity structures} }
Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)
Jean Cardinal, Timothy M. Chan, John Iacono, Stefan Langerman, and Aurélien Ooms. Subquadratic Encodings for Point Configurations. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 20:1-20:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{cardinal_et_al:LIPIcs.SoCG.2018.20, author = {Cardinal, Jean and Chan, Timothy M. and Iacono, John and Langerman, Stefan and Ooms, Aur\'{e}lien}, title = {{Subquadratic Encodings for Point Configurations}}, booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)}, pages = {20:1--20:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-066-8}, ISSN = {1868-8969}, year = {2018}, volume = {99}, editor = {Speckmann, Bettina and T\'{o}th, Csaba D.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.20}, URN = {urn:nbn:de:0030-drops-87337}, doi = {10.4230/LIPIcs.SoCG.2018.20}, annote = {Keywords: point configuration, order type, chirotope, succinct data structure} }
Published in: LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)
Jean Cardinal, Jerri Nummenpalo, and Emo Welzl. Solving and Sampling with Many Solutions: Satisfiability and Other Hard Problems. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 11:1-11:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{cardinal_et_al:LIPIcs.IPEC.2017.11, author = {Cardinal, Jean and Nummenpalo, Jerri and Welzl, Emo}, title = {{Solving and Sampling with Many Solutions: Satisfiability and Other Hard Problems}}, booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)}, pages = {11:1--11:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-051-4}, ISSN = {1868-8969}, year = {2018}, volume = {89}, editor = {Lokshtanov, Daniel and Nishimura, Naomi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.11}, URN = {urn:nbn:de:0030-drops-85459}, doi = {10.4230/LIPIcs.IPEC.2017.11}, annote = {Keywords: Satisfiability, Sampling, Parameterized complexity} }
Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)
Luis Barba, Jean Cardinal, John Iacono, Stefan Langerman, Aurélien Ooms, and Noam Solomon. Subquadratic Algorithms for Algebraic Generalizations of 3SUM. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 13:1-13:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{barba_et_al:LIPIcs.SoCG.2017.13, author = {Barba, Luis and Cardinal, Jean and Iacono, John and Langerman, Stefan and Ooms, Aur\'{e}lien and Solomon, Noam}, title = {{Subquadratic Algorithms for Algebraic Generalizations of 3SUM}}, booktitle = {33rd International Symposium on Computational Geometry (SoCG 2017)}, pages = {13:1--13:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-038-5}, ISSN = {1868-8969}, year = {2017}, volume = {77}, editor = {Aronov, Boris and Katz, Matthew J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.13}, URN = {urn:nbn:de:0030-drops-72214}, doi = {10.4230/LIPIcs.SoCG.2017.13}, annote = {Keywords: 3SUM, subquadratic algorithms, general position testing, range searching, dominance reporting, polynomial curves} }
Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)
Jean Cardinal, John Iacono, and Aurélien Ooms. Solving k-SUM Using Few Linear Queries. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 25:1-25:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{cardinal_et_al:LIPIcs.ESA.2016.25, author = {Cardinal, Jean and Iacono, John and Ooms, Aur\'{e}lien}, title = {{Solving k-SUM Using Few Linear Queries}}, booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)}, pages = {25:1--25:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-015-6}, ISSN = {1868-8969}, year = {2016}, volume = {57}, editor = {Sankowski, Piotr and Zaroliagis, Christos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.25}, URN = {urn:nbn:de:0030-drops-63763}, doi = {10.4230/LIPIcs.ESA.2016.25}, annote = {Keywords: k-SUM problem, linear decision trees, point location, \$varepsilon\$-nets} }
Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)
Jean Cardinal and Udo Hoffmann. Recognition and Complexity of Point Visibility Graphs. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 171-185, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2015)
@InProceedings{cardinal_et_al:LIPIcs.SOCG.2015.171, author = {Cardinal, Jean and Hoffmann, Udo}, title = {{Recognition and Complexity of Point Visibility Graphs}}, booktitle = {31st International Symposium on Computational Geometry (SoCG 2015)}, pages = {171--185}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-83-5}, ISSN = {1868-8969}, year = {2015}, volume = {34}, editor = {Arge, Lars and Pach, J\'{a}nos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.171}, URN = {urn:nbn:de:0030-drops-51390}, doi = {10.4230/LIPIcs.SOCG.2015.171}, annote = {Keywords: point visibility graphs, recognition, existential theory of the reals} }
Feedback for Dagstuhl Publishing