LIPIcs, Volume 258
SoCG 2023, June 12-15, 2023, Dallas, Texas, USA
Editors: Erin W. Chambers and Joachim Gudmundsson
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.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.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.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.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.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.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.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.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.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.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.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} }
Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)
Sayan Bandyapadhyay, Fedor V. Fomin, and Tanmay Inamdar. Coresets for Clustering in Geometric Intersection Graphs. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 10:1-10:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{bandyapadhyay_et_al:LIPIcs.SoCG.2023.10, author = {Bandyapadhyay, Sayan and Fomin, Fedor V. and Inamdar, Tanmay}, title = {{Coresets for Clustering in Geometric Intersection Graphs}}, booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)}, pages = {10:1--10: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.10}, URN = {urn:nbn:de:0030-drops-178605}, doi = {10.4230/LIPIcs.SoCG.2023.10}, annote = {Keywords: k-median, k-means, clustering, coresets, geometric graphs} }
Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)
Sayan Bandyapadhyay, William Lochet, Saket Saurabh, and Jie Xue. Minimum-Membership Geometric Set Cover, Revisited. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 11:1-11:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{bandyapadhyay_et_al:LIPIcs.SoCG.2023.11, author = {Bandyapadhyay, Sayan and Lochet, William and Saurabh, Saket and Xue, Jie}, title = {{Minimum-Membership Geometric Set Cover, Revisited}}, booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)}, pages = {11:1--11: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.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.11}, URN = {urn:nbn:de:0030-drops-178610}, doi = {10.4230/LIPIcs.SoCG.2023.11}, annote = {Keywords: geometric set cover, geometric optimization, approximation algorithms} }
Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)
Sayan Bandyapadhyay, William Lochet, and Saket Saurabh. FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 12:1-12:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{bandyapadhyay_et_al:LIPIcs.SoCG.2023.12, author = {Bandyapadhyay, Sayan and Lochet, William and Saurabh, Saket}, title = {{FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii}}, booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)}, pages = {12:1--12: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.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.12}, URN = {urn:nbn:de:0030-drops-178628}, doi = {10.4230/LIPIcs.SoCG.2023.12}, annote = {Keywords: Clustering, FPT-approximation} }
Feedback for Dagstuhl Publishing