LIPIcs, Volume 129
SoCG 2019, June 18-21, 2019, Portland, Oregon, USA
Editors: Gill Barequet and Yusu Wang
Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)
Aziz Burak Gülen, Facundo Mémoli, Zhengchao Wan, and Yusu Wang. A Generalization of the Persistent Laplacian to Simplicial Maps. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 37:1-37:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{gulen_et_al:LIPIcs.SoCG.2023.37, author = {G\"{u}len, Aziz Burak and M\'{e}moli, Facundo and Wan, Zhengchao and Wang, Yusu}, title = {{A Generalization of the Persistent Laplacian to Simplicial Maps}}, booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)}, pages = {37:1--37:17}, 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.37}, URN = {urn:nbn:de:0030-drops-178877}, doi = {10.4230/LIPIcs.SoCG.2023.37}, annote = {Keywords: combinatorial Laplacian, persistent Laplacian, Schur complement, persistent homology, persistent Betti number} }
Published in: LIPIcs, Volume 190, 19th International Symposium on Experimental Algorithms (SEA 2021)
Samantha Chen and Yusu Wang. Approximation Algorithms for 1-Wasserstein Distance Between Persistence Diagrams. In 19th International Symposium on Experimental Algorithms (SEA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 190, pp. 14:1-14:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{chen_et_al:LIPIcs.SEA.2021.14, author = {Chen, Samantha and Wang, Yusu}, title = {{Approximation Algorithms for 1-Wasserstein Distance Between Persistence Diagrams}}, booktitle = {19th International Symposium on Experimental Algorithms (SEA 2021)}, pages = {14:1--14:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-185-6}, ISSN = {1868-8969}, year = {2021}, volume = {190}, editor = {Coudert, David and Natale, Emanuele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2021.14}, URN = {urn:nbn:de:0030-drops-137861}, doi = {10.4230/LIPIcs.SEA.2021.14}, annote = {Keywords: persistence diagrams, approximation algorithms, Wasserstein distance, optimal transport} }
Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)
Ulrich Bauer, Claudia Landi, and Facundo Mémoli. The Reeb Graph Edit Distance Is Universal. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 15:1-15:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{bauer_et_al:LIPIcs.SoCG.2020.15, author = {Bauer, Ulrich and Landi, Claudia and M\'{e}moli, Facundo}, title = {{The Reeb Graph Edit Distance Is Universal}}, booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)}, pages = {15:1--15: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.15}, URN = {urn:nbn:de:0030-drops-121730}, doi = {10.4230/LIPIcs.SoCG.2020.15}, annote = {Keywords: Reeb graphs, topological descriptors, edit distance, interleaving distance} }
Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)
Chen Cai, Woojin Kim, Facundo Mémoli, and Yusu Wang. Elder-Rule-Staircodes for Augmented Metric Spaces. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 26:1-26:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{cai_et_al:LIPIcs.SoCG.2020.26, author = {Cai, Chen and Kim, Woojin and M\'{e}moli, Facundo and Wang, Yusu}, title = {{Elder-Rule-Staircodes for Augmented Metric Spaces}}, booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)}, pages = {26:1--26:17}, 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.26}, URN = {urn:nbn:de:0030-drops-121848}, doi = {10.4230/LIPIcs.SoCG.2020.26}, annote = {Keywords: Persistent homology, Multiparameter persistence, Barcodes, Elder rule, Hierarchical clustering, Graded Betti numbers} }
Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)
Tamal K. Dey, Tianqi Li, and Yusu Wang. An Efficient Algorithm for 1-Dimensional (Persistent) Path Homology. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 36:1-36:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{dey_et_al:LIPIcs.SoCG.2020.36, author = {Dey, Tamal K. and Li, Tianqi and Wang, Yusu}, title = {{An Efficient Algorithm for 1-Dimensional (Persistent) Path Homology}}, booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)}, pages = {36:1--36: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.36}, URN = {urn:nbn:de:0030-drops-121944}, doi = {10.4230/LIPIcs.SoCG.2020.36}, annote = {Keywords: computational topology, directed graph, path homology, persistent path homology} }
Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Matthew Kahle, Minghao Tian, and Yusu Wang. Local Cliques in ER-Perturbed Random Geometric Graphs. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 29:1-29:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{kahle_et_al:LIPIcs.ISAAC.2019.29, author = {Kahle, Matthew and Tian, Minghao and Wang, Yusu}, title = {{Local Cliques in ER-Perturbed Random Geometric Graphs}}, booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)}, pages = {29:1--29:22}, 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.29}, URN = {urn:nbn:de:0030-drops-115253}, doi = {10.4230/LIPIcs.ISAAC.2019.29}, annote = {Keywords: random graphs, random geometric graphs, edge clique number, the probabilistic method, metric recovery} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Elena Farahbakhsh Touli and Yusu Wang. FPT-Algorithms for Computing Gromov-Hausdorff and Interleaving Distances Between Trees. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 83:1-83:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{farahbakhshtouli_et_al:LIPIcs.ESA.2019.83, author = {Farahbakhsh Touli, Elena and Wang, Yusu}, title = {{FPT-Algorithms for Computing Gromov-Hausdorff and Interleaving Distances Between Trees}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {83:1--83:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-124-5}, ISSN = {1868-8969}, year = {2019}, volume = {144}, editor = {Bender, Michael A. and Svensson, Ola 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.2019.83}, URN = {urn:nbn:de:0030-drops-112048}, doi = {10.4230/LIPIcs.ESA.2019.83}, annote = {Keywords: Gromov-Hausdorff distance, Interleaving distance, Merge trees} }
Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)
Gill Barequet and Yusu Wang. LIPIcs, Volume 129, SoCG'19, Complete Volume. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@Proceedings{barequet_et_al:LIPIcs.SoCG.2019, title = {{LIPIcs, Volume 129, SoCG'19, Complete Volume}}, booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)}, 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}, URN = {urn:nbn:de:0030-drops-105562}, doi = {10.4230/LIPIcs.SoCG.2019}, annote = {Keywords: Theory of computation, Computational geometry, Design and analysis of algorithms, Mathematics of computing, Combinatorics, Graph algortihms} }
Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)
Gill Barequet and Yusu Wang. Front Matter, Table of Contents, Preface, Conference Organization. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 0:i-0:xvi, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{barequet_et_al:LIPIcs.SoCG.2019.0, author = {Barequet, Gill and Wang, Yusu}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)}, pages = {0:i--0:xvi}, 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.0}, URN = {urn:nbn:de:0030-drops-104047}, doi = {10.4230/LIPIcs.SoCG.2019.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)
Sanjoy Dasgupta. A Geometric Data Structure from Neuroscience (Invited Talk). In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, p. 1:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{dasgupta:LIPIcs.SoCG.2019.1, author = {Dasgupta, Sanjoy}, title = {{A Geometric Data Structure from Neuroscience}}, booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)}, pages = {1:1--1:1}, 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.1}, URN = {urn:nbn:de:0030-drops-104055}, doi = {10.4230/LIPIcs.SoCG.2019.1}, annote = {Keywords: Geometric data structure, algorithm design, neuroscience} }
Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)
Bruce R. Donald. Some Geometric and Computational Challenges Arising in Structural Molecular Biology (Invited Talk). In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 2:1-2:2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{donald:LIPIcs.SoCG.2019.2, author = {Donald, Bruce R.}, title = {{Some Geometric and Computational Challenges Arising in Structural Molecular Biology}}, booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)}, pages = {2:1--2:2}, 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.2}, URN = {urn:nbn:de:0030-drops-104065}, doi = {10.4230/LIPIcs.SoCG.2019.2}, annote = {Keywords: Geometric computing, combutational biology, Continuous Interdomain Orientation Distributions of Protein Conformations} }
Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)
Peyman Afshani. A New Lower Bound for Semigroup Orthogonal Range Searching. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 3:1-3:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{afshani:LIPIcs.SoCG.2019.3, author = {Afshani, Peyman}, title = {{A New Lower Bound for Semigroup Orthogonal Range Searching}}, booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)}, pages = {3:1--3:14}, 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.3}, URN = {urn:nbn:de:0030-drops-104075}, doi = {10.4230/LIPIcs.SoCG.2019.3}, annote = {Keywords: Data Structures, Range Searching, Lower bounds} }
Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)
Peyman Afshani and Jeff M. Phillips. Independent Range Sampling, Revisited Again. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 4:1-4:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{afshani_et_al:LIPIcs.SoCG.2019.4, author = {Afshani, Peyman and Phillips, Jeff M.}, title = {{Independent Range Sampling, Revisited Again}}, booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)}, pages = {4:1--4:13}, 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.4}, URN = {urn:nbn:de:0030-drops-104088}, doi = {10.4230/LIPIcs.SoCG.2019.4}, annote = {Keywords: Range Searching, Data Structures, Sampling} }
Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)
Pankaj K. Agarwal, Boris Aronov, Esther Ezra, and Joshua Zahl. An Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 5:1-5:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{agarwal_et_al:LIPIcs.SoCG.2019.5, author = {Agarwal, Pankaj K. and Aronov, Boris and Ezra, Esther and Zahl, Joshua}, title = {{An Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications}}, booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)}, pages = {5:1--5:14}, 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.5}, URN = {urn:nbn:de:0030-drops-104096}, doi = {10.4230/LIPIcs.SoCG.2019.5}, annote = {Keywords: Polynomial partitioning, quantifier elimination, semi-algebraic range spaces, epsilon-samples} }
Feedback for Dagstuhl Publishing