Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)
Emily Fox, Amir Nayyeri, Jonathan James Perry, and Benjamin Raichel. Fréchet Edit Distance. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 58:1-58:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{fox_et_al:LIPIcs.SoCG.2024.58, author = {Fox, Emily and Nayyeri, Amir and Perry, Jonathan James and Raichel, Benjamin}, title = {{Fr\'{e}chet Edit Distance}}, booktitle = {40th International Symposium on Computational Geometry (SoCG 2024)}, pages = {58:1--58: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.58}, URN = {urn:nbn:de:0030-drops-200032}, doi = {10.4230/LIPIcs.SoCG.2024.58}, annote = {Keywords: Fr\'{e}chet distance, Edit distance, Hardness} }
Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
Kyle Fox, Hongyao Huang, and Benjamin Raichel. Clustering with Faulty Centers. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{fox_et_al:LIPIcs.ISAAC.2022.10, author = {Fox, Kyle and Huang, Hongyao and Raichel, Benjamin}, title = {{Clustering with Faulty Centers}}, booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)}, pages = {10:1--10:14}, 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.10}, URN = {urn:nbn:de:0030-drops-172950}, doi = {10.4230/LIPIcs.ISAAC.2022.10}, annote = {Keywords: clustering, approximation, probabilistic input, uncertain input} }
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 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Hongyao Huang, Georgiy Klimenko, and Benjamin Raichel. Clustering with Neighborhoods. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 6:1-6:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{huang_et_al:LIPIcs.ISAAC.2021.6, author = {Huang, Hongyao and Klimenko, Georgiy and Raichel, Benjamin}, title = {{Clustering with Neighborhoods}}, booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, pages = {6:1--6:17}, 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.6}, URN = {urn:nbn:de:0030-drops-154398}, doi = {10.4230/LIPIcs.ISAAC.2021.6}, annote = {Keywords: Clustering, Approximation, Hardness} }
Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)
Georgiy Klimenko and Benjamin Raichel. Fast and Exact Convex Hull Simplification. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 26:1-26:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{klimenko_et_al:LIPIcs.FSTTCS.2021.26, author = {Klimenko, Georgiy and Raichel, Benjamin}, title = {{Fast and Exact Convex Hull Simplification}}, booktitle = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)}, pages = {26:1--26:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-215-0}, ISSN = {1868-8969}, year = {2021}, volume = {213}, editor = {Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.26}, URN = {urn:nbn:de:0030-drops-155373}, doi = {10.4230/LIPIcs.FSTTCS.2021.26}, annote = {Keywords: Convex hull, coreset, exact algorithm} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Chenglin Fan and Benjamin Raichel. Linear Expected Complexity for Directional and Multiplicative Voronoi Diagrams. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 45:1-45:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{fan_et_al:LIPIcs.ESA.2020.45, author = {Fan, Chenglin and Raichel, Benjamin}, title = {{Linear Expected Complexity for Directional and Multiplicative Voronoi Diagrams}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {45:1--45:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-162-7}, ISSN = {1868-8969}, year = {2020}, volume = {173}, editor = {Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.45}, URN = {urn:nbn:de:0030-drops-129111}, doi = {10.4230/LIPIcs.ESA.2020.45}, annote = {Keywords: Voronoi Diagrams, Expected Complexity, Computational Geometry} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Kevin Buchin, Chenglin Fan, Maarten Löffler, Aleksandr Popov, Benjamin Raichel, and Marcel Roeloffzen. Fréchet Distance for Uncertain Curves. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 20:1-20:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{buchin_et_al:LIPIcs.ICALP.2020.20, author = {Buchin, Kevin and Fan, Chenglin and L\"{o}ffler, Maarten and Popov, Aleksandr and Raichel, Benjamin and Roeloffzen, Marcel}, title = {{Fr\'{e}chet Distance for Uncertain Curves}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {20:1--20:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-138-2}, ISSN = {1868-8969}, year = {2020}, volume = {168}, editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.20}, URN = {urn:nbn:de:0030-drops-124276}, doi = {10.4230/LIPIcs.ICALP.2020.20}, annote = {Keywords: Curves, Uncertainty, Fr\'{e}chet Distance, Hardness} }
Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)
Chenglin Fan, Anna C. Gilbert, Benjamin Raichel, Rishi Sonthalia, and Gregory Van Buskirk. Generalized Metric Repair on Graphs. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 25:1-25:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{fan_et_al:LIPIcs.SWAT.2020.25, author = {Fan, Chenglin and Gilbert, Anna C. and Raichel, Benjamin and Sonthalia, Rishi and Van Buskirk, Gregory}, title = {{Generalized Metric Repair on Graphs}}, booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)}, pages = {25:1--25:22}, 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.25}, URN = {urn:nbn:de:0030-drops-122727}, doi = {10.4230/LIPIcs.SWAT.2020.25}, annote = {Keywords: Approximation, FPT, Hardness, Metric Spaces} }
Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Kyle Fox and Xinyi Li. Approximating the Geometric Edit Distance. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 23:1-23:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{fox_et_al:LIPIcs.ISAAC.2019.23, author = {Fox, Kyle and Li, Xinyi}, title = {{Approximating the Geometric Edit Distance}}, booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)}, pages = {23:1--23:16}, 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.23}, URN = {urn:nbn:de:0030-drops-115195}, doi = {10.4230/LIPIcs.ISAAC.2019.23}, annote = {Keywords: Geometric edit distance, Approximation, Randomized algorithms} }
Published in: LIPIcs, Volume 127, 22nd International Conference on Database Theory (ICDT 2019)
Nirman Kumar, Benjamin Raichel, Stavros Sintos, and Gregory Van Buskirk. Approximating Distance Measures for the Skyline. In 22nd International Conference on Database Theory (ICDT 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 127, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{kumar_et_al:LIPIcs.ICDT.2019.10, author = {Kumar, Nirman and Raichel, Benjamin and Sintos, Stavros and Van Buskirk, Gregory}, title = {{Approximating Distance Measures for the Skyline}}, booktitle = {22nd International Conference on Database Theory (ICDT 2019)}, pages = {10:1--10:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-101-6}, ISSN = {1868-8969}, year = {2019}, volume = {127}, editor = {Barcelo, Pablo and Calautti, Marco}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2019.10}, URN = {urn:nbn:de:0030-drops-103125}, doi = {10.4230/LIPIcs.ICDT.2019.10}, annote = {Keywords: Skyline, Pareto optimal, Approximation, Hardness, Multi-criteria decision making} }
Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)
Chenglin Fan and Benjamin Raichel. Computing the Fréchet Gap Distance. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 42:1-42:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{fan_et_al:LIPIcs.SoCG.2017.42, author = {Fan, Chenglin and Raichel, Benjamin}, title = {{Computing the Fr\'{e}chet Gap Distance}}, booktitle = {33rd International Symposium on Computational Geometry (SoCG 2017)}, pages = {42:1--42:16}, 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.42}, URN = {urn:nbn:de:0030-drops-71849}, doi = {10.4230/LIPIcs.SoCG.2017.42}, annote = {Keywords: Frechet Distance, Approximation, Polygonal Curves} }
Published in: LIPIcs, Volume 65, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)
Nirman Kumar, Benjamin Raichel, Subhash Suri, and Kevin Verbeek. Most Likely Voronoi Diagrams in Higher Dimensions. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 31:1-31:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{kumar_et_al:LIPIcs.FSTTCS.2016.31, author = {Kumar, Nirman and Raichel, Benjamin and Suri, Subhash and Verbeek, Kevin}, title = {{Most Likely Voronoi Diagrams in Higher Dimensions}}, booktitle = {36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)}, pages = {31:1--31:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-027-9}, ISSN = {1868-8969}, year = {2016}, volume = {65}, editor = {Lal, Akash and Akshay, S. and Saurabh, Saket and Sen, Sandeep}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2016.31}, URN = {urn:nbn:de:0030-drops-68667}, doi = {10.4230/LIPIcs.FSTTCS.2016.31}, annote = {Keywords: Uncertainty, Lower bounds, Voronoi Diagrams, Stochastic} }
Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)
Benjamin Raichel and C. Seshadhri. Avoiding the Global Sort: A Faster Contour Tree Algorithm. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 57:1-57:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{raichel_et_al:LIPIcs.SoCG.2016.57, author = {Raichel, Benjamin and Seshadhri, C.}, title = {{Avoiding the Global Sort: A Faster Contour Tree Algorithm}}, booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)}, pages = {57:1--57:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-009-5}, ISSN = {1868-8969}, year = {2016}, volume = {51}, editor = {Fekete, S\'{a}ndor and Lubiw, Anna}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.57}, URN = {urn:nbn:de:0030-drops-59490}, doi = {10.4230/LIPIcs.SoCG.2016.57}, annote = {Keywords: contour trees, computational topology, computational geometry} }
Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)
Sariel Har-Peled, Nirman Kumar, David M. Mount, and Benjamin Raichel. Space Exploration via Proximity Search. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 374-389, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{harpeled_et_al:LIPIcs.SOCG.2015.374, author = {Har-Peled, Sariel and Kumar, Nirman and Mount, David M. and Raichel, Benjamin}, title = {{Space Exploration via Proximity Search}}, booktitle = {31st International Symposium on Computational Geometry (SoCG 2015)}, pages = {374--389}, 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.374}, URN = {urn:nbn:de:0030-drops-51004}, doi = {10.4230/LIPIcs.SOCG.2015.374}, annote = {Keywords: Proximity search, implicit point set, probing} }
Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)
Hsien-Chih Chang, Sariel Har-Peled, and Benjamin Raichel. From Proximity to Utility: A Voronoi Partition of Pareto Optima. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 689-703, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{chang_et_al:LIPIcs.SOCG.2015.689, author = {Chang, Hsien-Chih and Har-Peled, Sariel and Raichel, Benjamin}, title = {{From Proximity to Utility: A Voronoi Partition of Pareto Optima}}, booktitle = {31st International Symposium on Computational Geometry (SoCG 2015)}, pages = {689--703}, 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.689}, URN = {urn:nbn:de:0030-drops-50925}, doi = {10.4230/LIPIcs.SOCG.2015.689}, annote = {Keywords: Voronoi diagrams, expected complexity, backward analysis, Pareto optima, candidate diagram, Clarkson-Shor technique} }
Feedback for Dagstuhl Publishing