LIPIcs, Volume 258
SoCG 2023, June 12-15, 2023, Dallas, Texas, USA
Editors: Erin W. Chambers and Joachim Gudmundsson
Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Joachim Gudmundsson, Zijin Huang, André van Renssen, and Sampson Wong. Computing a Subtrajectory Cluster from c-Packed Trajectories. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{gudmundsson_et_al:LIPIcs.ISAAC.2023.34, author = {Gudmundsson, Joachim and Huang, Zijin and van Renssen, Andr\'{e} and Wong, Sampson}, title = {{Computing a Subtrajectory Cluster from c-Packed Trajectories}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {34:1--34:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.34}, URN = {urn:nbn:de:0030-drops-193364}, doi = {10.4230/LIPIcs.ISAAC.2023.34}, annote = {Keywords: Subtrajectory cluster, c-packed trajectories, Computational geometry} }
Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Joachim Gudmundsson and Yuan Sha. Shortest Beer Path Queries in Digraphs with Bounded Treewidth. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 35:1-35:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{gudmundsson_et_al:LIPIcs.ISAAC.2023.35, author = {Gudmundsson, Joachim and Sha, Yuan}, title = {{Shortest Beer Path Queries in Digraphs with Bounded Treewidth}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {35:1--35:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.35}, URN = {urn:nbn:de:0030-drops-193379}, doi = {10.4230/LIPIcs.ISAAC.2023.35}, annote = {Keywords: Graph algorithms, Shortest Path, Data structures, Bounded treewidth} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Kevin Buchin, Joachim Gudmundsson, Antonia Kalb, Aleksandr Popov, Carolin Rehs, André van Renssen, and Sampson Wong. Oriented Spanners. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 26:1-26:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{buchin_et_al:LIPIcs.ESA.2023.26, author = {Buchin, Kevin and Gudmundsson, Joachim and Kalb, Antonia and Popov, Aleksandr and Rehs, Carolin and van Renssen, Andr\'{e} and Wong, Sampson}, title = {{Oriented Spanners}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {26:1--26:16}, 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.26}, URN = {urn:nbn:de:0030-drops-186796}, doi = {10.4230/LIPIcs.ESA.2023.26}, annote = {Keywords: computational geometry, spanner, oriented graph, greedy triangulation} }
Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)
39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 1-1058, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@Proceedings{chambers_et_al:LIPIcs.SoCG.2023, title = {{LIPIcs, Volume 258, SoCG 2023, Complete Volume}}, booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)}, pages = {1--1058}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023}, URN = {urn:nbn:de:0030-drops-178498}, doi = {10.4230/LIPIcs.SoCG.2023}, annote = {Keywords: LIPIcs, Volume 258, SoCG 2023, Complete Volume} }
Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)
39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 0:i-0:xx, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{chambers_et_al:LIPIcs.SoCG.2023.0, author = {Chambers, Erin W. and Gudmundsson, Joachim}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)}, pages = {0:i--0:xx}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.0}, URN = {urn:nbn:de:0030-drops-178501}, doi = {10.4230/LIPIcs.SoCG.2023.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)
Mikkel Abrahamsen, Linda Kleist, and Tillmann Miltzow. Geometric Embeddability of Complexes Is ∃ℝ-Complete. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 1:1-1:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{abrahamsen_et_al:LIPIcs.SoCG.2023.1, author = {Abrahamsen, Mikkel and Kleist, Linda and Miltzow, Tillmann}, title = {{Geometric Embeddability of Complexes Is \exists\mathbb{R}-Complete}}, booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)}, pages = {1:1--1:19}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.1}, URN = {urn:nbn:de:0030-drops-178518}, doi = {10.4230/LIPIcs.SoCG.2023.1}, annote = {Keywords: simplicial complex, geometric embedding, linear embedding, hypergraph, recognition, existential theory of the reals} }
Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)
Mikkel Abrahamsen and Bartosz Walczak. Distinguishing Classes of Intersection Graphs of Homothets or Similarities of Two Convex Disks. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 2:1-2:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{abrahamsen_et_al:LIPIcs.SoCG.2023.2, author = {Abrahamsen, Mikkel and Walczak, Bartosz}, title = {{Distinguishing Classes of Intersection Graphs of Homothets or Similarities of Two Convex Disks}}, booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)}, pages = {2:1--2: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.2}, URN = {urn:nbn:de:0030-drops-178523}, doi = {10.4230/LIPIcs.SoCG.2023.2}, annote = {Keywords: geometric intersection graph, convex disk, homothet, similarity} }
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-dev.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)
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-dev.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)
Pankaj K. Agarwal and Esther Ezra. Line Intersection Searching Amid Unit Balls in 3-Space. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{agarwal_et_al:LIPIcs.SoCG.2023.5, author = {Agarwal, Pankaj K. and Ezra, Esther}, title = {{Line Intersection Searching Amid Unit Balls in 3-Space}}, booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)}, pages = {5:1--5:14}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.5}, URN = {urn:nbn:de:0030-drops-178559}, doi = {10.4230/LIPIcs.SoCG.2023.5}, annote = {Keywords: Intersection searching, cylindrical range searching, partition trees, union of cylinders} }
Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)
Oswin Aichholzer, Man-Kwun Chiu, Hung P. Hoang, Michael Hoffmann, Jan Kynčl, Yannic Maus, Birgit Vogtenhuber, and Alexandra Weinberger. Drawings of Complete Multipartite Graphs up to Triangle Flips. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{aichholzer_et_al:LIPIcs.SoCG.2023.6, author = {Aichholzer, Oswin and Chiu, Man-Kwun and Hoang, Hung P. and Hoffmann, Michael and Kyn\v{c}l, Jan and Maus, Yannic and Vogtenhuber, Birgit and Weinberger, Alexandra}, title = {{Drawings of Complete Multipartite Graphs up to Triangle Flips}}, booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)}, pages = {6:1--6: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.6}, URN = {urn:nbn:de:0030-drops-178563}, doi = {10.4230/LIPIcs.SoCG.2023.6}, annote = {Keywords: Simple drawings, simple topological graphs, complete graphs, multipartite graphs, k-partite graphs, bipartite graphs, Gioan’s Theorem, triangle flips, Reidemeister moves} }
Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)
Ángel Javier Alonso and Michael Kerber. Decomposition of Zero-Dimensional Persistence Modules via Rooted Subsets. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{alonso_et_al:LIPIcs.SoCG.2023.7, author = {Alonso, \'{A}ngel Javier and Kerber, Michael}, title = {{Decomposition of Zero-Dimensional Persistence Modules via Rooted Subsets}}, booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)}, pages = {7:1--7: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.7}, URN = {urn:nbn:de:0030-drops-178570}, doi = {10.4230/LIPIcs.SoCG.2023.7}, annote = {Keywords: Multiparameter persistent homology, Clustering, Decomposition of persistence modules, Elder Rule} }
Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)
Gergely Ambrus, Martin Balko, Nóra Frankl, Attila Jung, and Márton Naszódi. On Helly Numbers of Exponential Lattices. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{ambrus_et_al:LIPIcs.SoCG.2023.8, author = {Ambrus, Gergely and Balko, Martin and Frankl, N\'{o}ra and Jung, Attila and Nasz\'{o}di, M\'{a}rton}, title = {{On Helly Numbers of Exponential Lattices}}, booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)}, pages = {8:1--8: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.8}, URN = {urn:nbn:de:0030-drops-178584}, doi = {10.4230/LIPIcs.SoCG.2023.8}, annote = {Keywords: Helly numbers, exponential lattices, Diophantine approximation} }
Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)
Sunil Arya and David M. Mount. Optimal Volume-Sensitive Bounds for Polytope Approximation. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{arya_et_al:LIPIcs.SoCG.2023.9, author = {Arya, Sunil and Mount, David M.}, title = {{Optimal Volume-Sensitive Bounds for Polytope Approximation}}, booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)}, pages = {9:1--9: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.9}, URN = {urn:nbn:de:0030-drops-178592}, doi = {10.4230/LIPIcs.SoCG.2023.9}, annote = {Keywords: Approximation algorithms, convexity, Macbeath regions} }
Feedback for Dagstuhl Publishing