Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Timothy M. Chan, Qizheng He, and Yuancheng Yu. On the Fine-Grained Complexity of Small-Size Geometric Set Cover and Discrete k-Center for Small k. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 34:1-34:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{chan_et_al:LIPIcs.ICALP.2023.34, author = {Chan, Timothy M. and He, Qizheng and Yu, Yuancheng}, title = {{On the Fine-Grained Complexity of Small-Size Geometric Set Cover and Discrete k-Center for Small k}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {34:1--34:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.34}, URN = {urn:nbn:de:0030-drops-180868}, doi = {10.4230/LIPIcs.ICALP.2023.34}, annote = {Keywords: Geometric set cover, discrete k-center, conditional lower bounds} }
Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)
Timothy M. Chan and Zhengcheng Huang. Constant-Hop Spanners for More Geometric Intersection Graphs, with Even Smaller Size. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 23:1-23:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{chan_et_al:LIPIcs.SoCG.2023.23, author = {Chan, Timothy M. and Huang, Zhengcheng}, title = {{Constant-Hop Spanners for More Geometric Intersection Graphs, with Even Smaller Size}}, booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)}, pages = {23:1--23: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.23}, URN = {urn:nbn:de:0030-drops-178738}, doi = {10.4230/LIPIcs.SoCG.2023.23}, annote = {Keywords: Hop spanners, geometric intersection graphs, string graphs, fat objects, separators, shallow cuttings} }
Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)
Timothy M. Chan. Minimum L_∞ Hausdorff Distance of Point Sets Under Translation: Generalizing Klee’s Measure Problem. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 24:1-24:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{chan:LIPIcs.SoCG.2023.24, author = {Chan, Timothy M.}, title = {{Minimum L\underline∞ Hausdorff Distance of Point Sets Under Translation: Generalizing Klee’s Measure Problem}}, booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)}, pages = {24:1--24:13}, 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.24}, URN = {urn:nbn:de:0030-drops-178741}, doi = {10.4230/LIPIcs.SoCG.2023.24}, annote = {Keywords: Hausdorff distance, geometric optimization, Klee’s measure problem, fine-grained complexity} }
Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Timothy M. Chan. All-Pairs Shortest Paths for Real-Weighted Undirected Graphs with Small Additive Error. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 27:1-27:9, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{chan:LIPIcs.ESA.2021.27, author = {Chan, Timothy M.}, title = {{All-Pairs Shortest Paths for Real-Weighted Undirected Graphs with Small Additive Error}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {27:1--27:9}, 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.27}, URN = {urn:nbn:de:0030-drops-146086}, doi = {10.4230/LIPIcs.ESA.2021.27}, annote = {Keywords: Shortest paths, approximation, matrix multiplication} }
Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Timothy M. Chan and Zhengcheng Huang. Dynamic Colored Orthogonal Range Searching. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 28:1-28:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{chan_et_al:LIPIcs.ESA.2021.28, author = {Chan, Timothy M. and Huang, Zhengcheng}, title = {{Dynamic Colored Orthogonal Range Searching}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {28:1--28:13}, 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.28}, URN = {urn:nbn:de:0030-drops-146090}, doi = {10.4230/LIPIcs.ESA.2021.28}, annote = {Keywords: Range searching, dynamic data structures, word RAM} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Timothy M. Chan, Virginia Vassilevska Williams, and Yinzhan Xu. Algorithms, Reductions and Equivalences for Small Weight Variants of All-Pairs Shortest Paths. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 47:1-47:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{chan_et_al:LIPIcs.ICALP.2021.47, author = {Chan, Timothy M. and Vassilevska Williams, Virginia and Xu, Yinzhan}, title = {{Algorithms, Reductions and Equivalences for Small Weight Variants of All-Pairs Shortest Paths}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {47:1--47:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.47}, URN = {urn:nbn:de:0030-drops-141166}, doi = {10.4230/LIPIcs.ICALP.2021.47}, annote = {Keywords: All-Pairs Shortest Paths, Fine-Grained Complexity, Graph Algorithm} }
Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)
Virginia Vassilevska Williams. 3SUM and Related Problems in Fine-Grained Complexity (Invited Talk). In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 2:1-2:2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{vassilevskawilliams:LIPIcs.SoCG.2021.2, author = {Vassilevska Williams, Virginia}, title = {{3SUM and Related Problems in Fine-Grained Complexity}}, booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)}, pages = {2:1--2:2}, 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.2}, URN = {urn:nbn:de:0030-drops-138014}, doi = {10.4230/LIPIcs.SoCG.2021.2}, annote = {Keywords: fine-grained complexity} }
Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)
Timothy M. Chan. Faster Algorithms for Largest Empty Rectangles and Boxes. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 24:1-24:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{chan:LIPIcs.SoCG.2021.24, author = {Chan, Timothy M.}, title = {{Faster Algorithms for Largest Empty Rectangles and Boxes}}, booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)}, pages = {24:1--24: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.24}, URN = {urn:nbn:de:0030-drops-138231}, doi = {10.4230/LIPIcs.SoCG.2021.24}, annote = {Keywords: Largest empty rectangle, largest empty box, Klee’s measure problem} }
Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)
Timothy M. Chan and Qizheng He. More Dynamic Data Structures for Geometric Set Cover with Sublinear Update Time. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 25:1-25:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{chan_et_al:LIPIcs.SoCG.2021.25, author = {Chan, Timothy M. and He, Qizheng}, title = {{More Dynamic Data Structures for Geometric Set Cover with Sublinear Update Time}}, booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)}, pages = {25:1--25: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.25}, URN = {urn:nbn:de:0030-drops-138244}, doi = {10.4230/LIPIcs.SoCG.2021.25}, annote = {Keywords: Geometric set cover, approximation algorithms, dynamic data structures, sublinear algorithms, random sampling} }
Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Timothy M. Chan and Saladi Rahul. Simple Multi-Pass Streaming Algorithms for Skyline Points and Extreme Points. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 22:1-22:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{chan_et_al:LIPIcs.STACS.2021.22, author = {Chan, Timothy M. and Rahul, Saladi}, title = {{Simple Multi-Pass Streaming Algorithms for Skyline Points and Extreme Points}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {22:1--22:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-180-1}, ISSN = {1868-8969}, year = {2021}, volume = {187}, editor = {Bl\"{a}ser, Markus and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.22}, URN = {urn:nbn:de:0030-drops-136674}, doi = {10.4230/LIPIcs.STACS.2021.22}, annote = {Keywords: multi-pass streaming algorithms, skyline, convex hull, extreme points, randomized algorithms} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Timothy M. Chan and Qizheng He. More on Change-Making and Related Problems. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 29:1-29:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{chan_et_al:LIPIcs.ESA.2020.29, author = {Chan, Timothy M. and He, Qizheng}, title = {{More on Change-Making and Related Problems}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {29:1--29:14}, 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.29}, URN = {urn:nbn:de:0030-drops-128958}, doi = {10.4230/LIPIcs.ESA.2020.29}, annote = {Keywords: Coin changing, knapsack, dynamic programming, Frobenius problem, fine-grained complexity} }
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)
Timothy M. Chan and Qizheng He. Faster Approximation Algorithms for Geometric Set Cover. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 27:1-27:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{chan_et_al:LIPIcs.SoCG.2020.27, author = {Chan, Timothy M. and He, Qizheng}, title = {{Faster Approximation Algorithms for Geometric Set Cover}}, booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)}, pages = {27:1--27: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.27}, URN = {urn:nbn:de:0030-drops-121856}, doi = {10.4230/LIPIcs.SoCG.2020.27}, annote = {Keywords: Set cover, approximation algorithms, multiplicate weight update method, random sampling, shallow cuttings} }
Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)
Timothy M. Chan, Qizheng He, and Yakov Nekrich. Further Results on Colored Range Searching. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 28:1-28:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{chan_et_al:LIPIcs.SoCG.2020.28, author = {Chan, Timothy M. and He, Qizheng and Nekrich, Yakov}, title = {{Further Results on Colored Range Searching}}, booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)}, pages = {28:1--28: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.28}, URN = {urn:nbn:de:0030-drops-121868}, doi = {10.4230/LIPIcs.SoCG.2020.28}, annote = {Keywords: Range searching, geometric data structures, randomized incremental construction, random sampling, word RAM} }
Published in: LIPIcs, Volume 143, 19th International Workshop on Algorithms in Bioinformatics (WABI 2019)
Natalie Sauerwald, Yihang Shen, and Carl Kingsford. Topological Data Analysis Reveals Principles of Chromosome Structure in Cellular Differentiation. In 19th International Workshop on Algorithms in Bioinformatics (WABI 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 143, pp. 23:1-23:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{sauerwald_et_al:LIPIcs.WABI.2019.23, author = {Sauerwald, Natalie and Shen, Yihang and Kingsford, Carl}, title = {{Topological Data Analysis Reveals Principles of Chromosome Structure in Cellular Differentiation}}, booktitle = {19th International Workshop on Algorithms in Bioinformatics (WABI 2019)}, pages = {23:1--23:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-123-8}, ISSN = {1868-8969}, year = {2019}, volume = {143}, editor = {Huber, Katharina T. and Gusfield, Dan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2019.23}, URN = {urn:nbn:de:0030-drops-110537}, doi = {10.4230/LIPIcs.WABI.2019.23}, annote = {Keywords: topological data analysis, chromosome structure, Hi-C, topologically associating domains} }
Feedback for Dagstuhl Publishing