LIPIcs, Volume 212
ISAAC 2021, December 6-8, 2021, Fukuoka, Japan
Editors: Hee-Kap Ahn and Kunihiko Sadakane
Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)
Jaehoon Chung, Sang Won Bae, Chan-Su Shin, Sang Duk Yoon, and Hee-Kap Ahn. Inscribing or Circumscribing a Histogon to a Convex Polygon. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{chung_et_al:LIPIcs.FSTTCS.2022.13, author = {Chung, Jaehoon and Bae, Sang Won and Shin, Chan-Su and Yoon, Sang Duk and Ahn, Hee-Kap}, title = {{Inscribing or Circumscribing a Histogon to a Convex Polygon}}, booktitle = {42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)}, pages = {13:1--13:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-261-7}, ISSN = {1868-8969}, year = {2022}, volume = {250}, editor = {Dawar, Anuj and Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.13}, URN = {urn:nbn:de:0030-drops-174054}, doi = {10.4230/LIPIcs.FSTTCS.2022.13}, annote = {Keywords: Shape simplification, Shape analysis, Histogon, Convex polygon} }
Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)
Mincheol Kim, Chanyang Seo, Taehoon Ahn, and Hee-Kap Ahn. Farthest-Point Voronoi Diagrams in the Presence of Rectangular Obstacles. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 51:1-51:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{kim_et_al:LIPIcs.SoCG.2022.51, author = {Kim, Mincheol and Seo, Chanyang and Ahn, Taehoon and Ahn, Hee-Kap}, title = {{Farthest-Point Voronoi Diagrams in the Presence of Rectangular Obstacles}}, booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)}, pages = {51:1--51:15}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.51}, URN = {urn:nbn:de:0030-drops-160596}, doi = {10.4230/LIPIcs.SoCG.2022.51}, annote = {Keywords: Geodesic distance, L₁ metric, farthest-point Voronoi diagram} }
Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 1-1188, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@Proceedings{ahn_et_al:LIPIcs.ISAAC.2021, title = {{LIPIcs, Volume 212, ISAAC 2021, Complete Volume}}, booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, pages = {1--1188}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021}, URN = {urn:nbn:de:0030-drops-154329}, doi = {10.4230/LIPIcs.ISAAC.2021}, annote = {Keywords: LIPIcs, Volume 212, ISAAC 2021, Complete Volume} }
Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 0:i-0:xviii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{ahn_et_al:LIPIcs.ISAAC.2021.0, author = {Ahn, Hee-Kap and Sadakane, Kunihiko}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, pages = {0:i--0:xviii}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.0}, URN = {urn:nbn:de:0030-drops-154330}, doi = {10.4230/LIPIcs.ISAAC.2021.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Tatiana Starikovskaya. Streaming Pattern Matching (Invited Talk). In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{starikovskaya:LIPIcs.ISAAC.2021.1, author = {Starikovskaya, Tatiana}, title = {{Streaming Pattern Matching}}, booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, pages = {1:1--1:1}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.1}, URN = {urn:nbn:de:0030-drops-154345}, doi = {10.4230/LIPIcs.ISAAC.2021.1}, annote = {Keywords: Streaming algorithms, Pattern matching, Hamming distance, Edit distance} }
Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Prosenjit Bose. Spanning Properties of Variants of the Delaunay Graph (Invited Talk). In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{bose:LIPIcs.ISAAC.2021.2, author = {Bose, Prosenjit}, title = {{Spanning Properties of Variants of the Delaunay Graph}}, booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, pages = {2:1--2:1}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.2}, URN = {urn:nbn:de:0030-drops-154352}, doi = {10.4230/LIPIcs.ISAAC.2021.2}, annote = {Keywords: Delaunay Graph, Geometric Graph, Graph Spanner} }
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-dev.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 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Michael Matheny and Jeff M. Phillips. Approximate Maximum Halfspace Discrepancy. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{matheny_et_al:LIPIcs.ISAAC.2021.4, author = {Matheny, Michael and Phillips, Jeff M.}, title = {{Approximate Maximum Halfspace Discrepancy}}, booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, pages = {4:1--4: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.4}, URN = {urn:nbn:de:0030-drops-154377}, doi = {10.4230/LIPIcs.ISAAC.2021.4}, annote = {Keywords: range spaces, halfspaces, scan statistics, fine-grained complexity} }
Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Matt Gibson-Lopez and Zhongxiu Yang. The VC-Dimension of Limited Visibility Terrains. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 5:1-5:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{gibsonlopez_et_al:LIPIcs.ISAAC.2021.5, author = {Gibson-Lopez, Matt and Yang, Zhongxiu}, title = {{The VC-Dimension of Limited Visibility Terrains}}, booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, pages = {5:1--5:17}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.5}, URN = {urn:nbn:de:0030-drops-154386}, doi = {10.4230/LIPIcs.ISAAC.2021.5}, annote = {Keywords: VC-dimension, Terrain Guarding, Limited Visibility} }
Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Hongyao Huang, Georgiy Klimenko, and Benjamin Raichel. Clustering with Neighborhoods. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 6:1-6:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{huang_et_al:LIPIcs.ISAAC.2021.6, author = {Huang, Hongyao and Klimenko, Georgiy and Raichel, Benjamin}, title = {{Clustering with Neighborhoods}}, booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, pages = {6:1--6:17}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.6}, URN = {urn:nbn:de:0030-drops-154398}, doi = {10.4230/LIPIcs.ISAAC.2021.6}, annote = {Keywords: Clustering, Approximation, Hardness} }
Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Ahmad Biniaz. Approximating Longest Spanning Tree with Neighborhoods. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 7:1-7:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{biniaz:LIPIcs.ISAAC.2021.7, author = {Biniaz, Ahmad}, title = {{Approximating Longest Spanning Tree with Neighborhoods}}, booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, pages = {7:1--7:11}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.7}, URN = {urn:nbn:de:0030-drops-154401}, doi = {10.4230/LIPIcs.ISAAC.2021.7}, annote = {Keywords: Euclidean maximum spanning tree, spanning tree with neighborhoods, approximation algorithms} }
Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Siu-Wing Cheng and Man Ting Wong. Self-Improving Voronoi Construction for a Hidden Mixture of Product Distributions. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 8:1-8:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{cheng_et_al:LIPIcs.ISAAC.2021.8, author = {Cheng, Siu-Wing and Wong, Man Ting}, title = {{Self-Improving Voronoi Construction for a Hidden Mixture of Product Distributions}}, booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, pages = {8:1--8:13}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.8}, URN = {urn:nbn:de:0030-drops-154418}, doi = {10.4230/LIPIcs.ISAAC.2021.8}, annote = {Keywords: entropy, Voronoi diagram, convex distance function, hidden mixture of product distributions} }
Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Sándor P. Fekete, Phillip Keldenich, Ramin Kosfeld, Christian Rieck, and Christian Scheffer. Connected Coordinated Motion Planning with Bounded Stretch. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{fekete_et_al:LIPIcs.ISAAC.2021.9, author = {Fekete, S\'{a}ndor P. and Keldenich, Phillip and Kosfeld, Ramin and Rieck, Christian and Scheffer, Christian}, title = {{Connected Coordinated Motion Planning with Bounded Stretch}}, booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, pages = {9:1--9:16}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.9}, URN = {urn:nbn:de:0030-drops-154423}, doi = {10.4230/LIPIcs.ISAAC.2021.9}, annote = {Keywords: Motion planning, parallel motion, bounded stretch, scaled shape, makespan, connectivity, swarm robotics} }
Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Patrick Schnider. Enclosing Depth and Other Depth Measures. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 10:1-10:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{schnider:LIPIcs.ISAAC.2021.10, author = {Schnider, Patrick}, title = {{Enclosing Depth and Other Depth Measures}}, booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, pages = {10:1--10: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.10}, URN = {urn:nbn:de:0030-drops-154431}, doi = {10.4230/LIPIcs.ISAAC.2021.10}, annote = {Keywords: Depth measures, Tukey depth, Tverberg theorem, Combinatorial Geometry} }
Feedback for Dagstuhl Publishing