Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)
Pankaj K. Agarwal and Sariel Har-Peled. Computing Instance-Optimal Kernels in Two Dimensions. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 4:1-4:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{agarwal_et_al:LIPIcs.SoCG.2023.4, author = {Agarwal, Pankaj K. and Har-Peled, Sariel}, title = {{Computing Instance-Optimal Kernels in Two Dimensions}}, booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)}, pages = {4:1--4:15}, 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.4}, URN = {urn:nbn:de:0030-drops-178544}, doi = {10.4230/LIPIcs.SoCG.2023.4}, annote = {Keywords: Coreset, approximation, kernel} }
Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)
Oliver A. Chubet, Paul Macnichol, Parth Parikh, Donald R. Sheehy, and Siddharth S. Sheth. Greedy Permutations and Finite Voronoi Diagrams (Media Exposition). In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 64:1-64:5, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{chubet_et_al:LIPIcs.SoCG.2023.64, author = {Chubet, Oliver A. and Macnichol, Paul and Parikh, Parth and Sheehy, Donald R. and Sheth, Siddharth S.}, title = {{Greedy Permutations and Finite Voronoi Diagrams}}, booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)}, pages = {64:1--64:5}, 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.64}, URN = {urn:nbn:de:0030-drops-179146}, doi = {10.4230/LIPIcs.SoCG.2023.64}, annote = {Keywords: greedy permutation, Voronoi diagrams} }
Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)
Sariel Har-Peled and Everett Yang. Approximation Algorithms for Maximum Matchings in Geometric Intersection Graphs. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 47:1-47:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{harpeled_et_al:LIPIcs.SoCG.2022.47, author = {Har-Peled, Sariel and Yang, Everett}, title = {{Approximation Algorithms for Maximum Matchings in Geometric Intersection Graphs}}, booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)}, pages = {47:1--47:13}, 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.47}, URN = {urn:nbn:de:0030-drops-160555}, doi = {10.4230/LIPIcs.SoCG.2022.47}, annote = {Keywords: Matchings, disk intersection graphs, approximation algorithms} }
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 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Sariel Har-Peled and Timothy Zhou. Improved Approximation Algorithms for Tverberg Partitions. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 51:1-51:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{harpeled_et_al:LIPIcs.ESA.2021.51, author = {Har-Peled, Sariel and Zhou, Timothy}, title = {{Improved Approximation Algorithms for Tverberg Partitions}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {51:1--51: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.51}, URN = {urn:nbn:de:0030-drops-146323}, doi = {10.4230/LIPIcs.ESA.2021.51}, annote = {Keywords: Geometric spanners, vertex failures, robustness} }
Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)
Stav Ashur and Sariel Har-Peled. On Undecided LP, Clustering and Active Learning. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 12:1-12:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{ashur_et_al:LIPIcs.SoCG.2021.12, author = {Ashur, Stav and Har-Peled, Sariel}, title = {{On Undecided LP, Clustering and Active Learning}}, booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)}, pages = {12:1--12: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.12}, URN = {urn:nbn:de:0030-drops-138116}, doi = {10.4230/LIPIcs.SoCG.2021.12}, annote = {Keywords: Linear Programming, Active learning, Classification} }
Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)
Sariel Har-Peled and Mitchell Jones. Stabbing Convex Bodies with Lines and Flats. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 42:1-42:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{harpeled_et_al:LIPIcs.SoCG.2021.42, author = {Har-Peled, Sariel and Jones, Mitchell}, title = {{Stabbing Convex Bodies with Lines and Flats}}, booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)}, pages = {42:1--42:12}, 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.42}, URN = {urn:nbn:de:0030-drops-138412}, doi = {10.4230/LIPIcs.SoCG.2021.42}, annote = {Keywords: Discrete geometry, combinatorics, weak \epsilon-nets, k-flats} }
Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)
Sariel Har-Peled, Manor Mendel, and Dániel Oláh. Reliable Spanners for Metric Spaces. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 43:1-43:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{harpeled_et_al:LIPIcs.SoCG.2021.43, author = {Har-Peled, Sariel and Mendel, Manor and Ol\'{a}h, D\'{a}niel}, title = {{Reliable Spanners for Metric Spaces}}, booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)}, pages = {43:1--43:13}, 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.43}, URN = {urn:nbn:de:0030-drops-138423}, doi = {10.4230/LIPIcs.SoCG.2021.43}, annote = {Keywords: Spanners, reliability} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Kevin Buchin, Sariel Har-Peled, and Dániel Oláh. Sometimes Reliable Spanners of Almost Linear Size. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 27:1-27:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{buchin_et_al:LIPIcs.ESA.2020.27, author = {Buchin, Kevin and Har-Peled, Sariel and Ol\'{a}h, D\'{a}niel}, title = {{Sometimes Reliable Spanners of Almost Linear Size}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {27:1--27:15}, 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.27}, URN = {urn:nbn:de:0030-drops-128934}, doi = {10.4230/LIPIcs.ESA.2020.27}, annote = {Keywords: Geometric spanners, vertex failures, reliability} }
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)
Sariel Har-Peled, Mitchell Jones, and Saladi Rahul. Active Learning a Convex Body in Low Dimensions. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 64:1-64:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{harpeled_et_al:LIPIcs.ICALP.2020.64, author = {Har-Peled, Sariel and Jones, Mitchell and Rahul, Saladi}, title = {{Active Learning a Convex Body in Low Dimensions}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {64:1--64:17}, 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.64}, URN = {urn:nbn:de:0030-drops-124711}, doi = {10.4230/LIPIcs.ICALP.2020.64}, annote = {Keywords: Approximation algorithms, computational geometry, separation oracles, active learning} }
Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)
Arturs Backurs and Sariel Har-Peled. Submodular Clustering in Low Dimensions. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 8:1-8:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{backurs_et_al:LIPIcs.SWAT.2020.8, author = {Backurs, Arturs and Har-Peled, Sariel}, title = {{Submodular Clustering in Low Dimensions}}, booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)}, pages = {8:1--8:14}, 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.8}, URN = {urn:nbn:de:0030-drops-122551}, doi = {10.4230/LIPIcs.SWAT.2020.8}, annote = {Keywords: clustering, covering, PTAS} }
Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)
Sariel Har-Peled and Mitchell Jones. Fast Algorithms for Geometric Consensuses. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 50:1-50:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{harpeled_et_al:LIPIcs.SoCG.2020.50, author = {Har-Peled, Sariel and Jones, Mitchell}, title = {{Fast Algorithms for Geometric Consensuses}}, booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)}, pages = {50:1--50:16}, 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.50}, URN = {urn:nbn:de:0030-drops-122088}, doi = {10.4230/LIPIcs.SoCG.2020.50}, annote = {Keywords: Geometric optimization, centerpoint, voting games} }
Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)
Kevin Buchin, Sariel Har-Peled, and Dániel Oláh. A Spanner for the Day After. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 19:1-19:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{buchin_et_al:LIPIcs.SoCG.2019.19, author = {Buchin, Kevin and Har-Peled, Sariel and Ol\'{a}h, D\'{a}niel}, title = {{A Spanner for the Day After}}, booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)}, pages = {19:1--19:15}, 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.19}, URN = {urn:nbn:de:0030-drops-104237}, doi = {10.4230/LIPIcs.SoCG.2019.19}, annote = {Keywords: Geometric spanners, vertex failures, robustness} }
Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)
Sergio Cabello and Timothy M. Chan. Computing Shapley Values in the Plane. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 20:1-20:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{cabello_et_al:LIPIcs.SoCG.2019.20, author = {Cabello, Sergio and Chan, Timothy M.}, title = {{Computing Shapley Values in the Plane}}, booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)}, pages = {20:1--20:19}, 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.20}, URN = {urn:nbn:de:0030-drops-104244}, doi = {10.4230/LIPIcs.SoCG.2019.20}, annote = {Keywords: Shapley values, stochastic computational geometry, convex hull, minimum enclosing disk, bounding box, arrangements, convolutions, airport problem} }
Feedback for Dagstuhl Publishing