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} }
Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)
Micha Sharir and Noam Solomon. On Rich Points and Incidences with Restricted Sets of Lines in 3-Space. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 56:1-56:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{sharir_et_al:LIPIcs.SoCG.2021.56, author = {Sharir, Micha and Solomon, Noam}, title = {{On Rich Points and Incidences with Restricted Sets of Lines in 3-Space}}, booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)}, pages = {56:1--56:14}, 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.56}, URN = {urn:nbn:de:0030-drops-138551}, doi = {10.4230/LIPIcs.SoCG.2021.56}, annote = {Keywords: Lines in space, Rich points, Polynomial partitioning, Incidences} }
Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)
Haim Kaplan and Jay Tenenbaum. Locality Sensitive Hashing for Set-Queries, Motivated by Group Recommendations. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 28:1-28:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{kaplan_et_al:LIPIcs.SWAT.2020.28, author = {Kaplan, Haim and Tenenbaum, Jay}, title = {{Locality Sensitive Hashing for Set-Queries, Motivated by Group Recommendations}}, booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)}, pages = {28:1--28:18}, 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.28}, URN = {urn:nbn:de:0030-drops-122756}, doi = {10.4230/LIPIcs.SWAT.2020.28}, annote = {Keywords: Locality sensitive hashing, nearest neighbors, similarity search, group recommendations, distance functions, similarity functions, ellipsoid} }
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 164, 36th International Symposium on Computational Geometry (SoCG 2020)
Haim Kaplan, Micha Sharir, and Uri Stemmer. How to Find a Point in the Convex Hull Privately. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 52:1-52:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{kaplan_et_al:LIPIcs.SoCG.2020.52, author = {Kaplan, Haim and Sharir, Micha and Stemmer, Uri}, title = {{How to Find a Point in the Convex Hull Privately}}, booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)}, pages = {52:1--52:15}, 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.52}, URN = {urn:nbn:de:0030-drops-122107}, doi = {10.4230/LIPIcs.SoCG.2020.52}, annote = {Keywords: Differential privacy, Tukey depth, Convex hull} }
Feedback for Dagstuhl Publishing