Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
Vladimirs Andrejevs, Aleksandrs Belovs, and Jevgēnijs Vihrovs. Quantum Algorithms for Hopcroft’s Problem. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{andrejevs_et_al:LIPIcs.MFCS.2024.9, author = {Andrejevs, Vladimirs and Belovs, Aleksandrs and Vihrovs, Jevg\={e}nijs}, title = {{Quantum Algorithms for Hopcroft’s Problem}}, booktitle = {49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)}, pages = {9:1--9:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-335-5}, ISSN = {1868-8969}, year = {2024}, volume = {306}, editor = {Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.9}, URN = {urn:nbn:de:0030-drops-205653}, doi = {10.4230/LIPIcs.MFCS.2024.9}, annote = {Keywords: Quantum algorithms, Quantum walks, Computational Geometry} }
Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
Nathan van Beusekom, Marc van Kreveld, Max van Mulken, Marcel Roeloffzen, Bettina Speckmann, and Jules Wulms. Capturing the Shape of a Point Set with a Line Segment. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 26:1-26:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{vanbeusekom_et_al:LIPIcs.MFCS.2024.26, author = {van Beusekom, Nathan and van Kreveld, Marc and van Mulken, Max and Roeloffzen, Marcel and Speckmann, Bettina and Wulms, Jules}, title = {{Capturing the Shape of a Point Set with a Line Segment}}, booktitle = {49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)}, pages = {26:1--26:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-335-5}, ISSN = {1868-8969}, year = {2024}, volume = {306}, editor = {Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.26}, URN = {urn:nbn:de:0030-drops-205820}, doi = {10.4230/LIPIcs.MFCS.2024.26}, annote = {Keywords: Shape descriptor, Stabbing, Rotating calipers} }
Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
Gang Liu and Haitao Wang. Unweighted Geometric Hitting Set for Line-Constrained Disks and Related Problems. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 68:1-68:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{liu_et_al:LIPIcs.MFCS.2024.68, author = {Liu, Gang and Wang, Haitao}, title = {{Unweighted Geometric Hitting Set for Line-Constrained Disks and Related Problems}}, booktitle = {49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)}, pages = {68:1--68:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-335-5}, ISSN = {1868-8969}, year = {2024}, volume = {306}, editor = {Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.68}, URN = {urn:nbn:de:0030-drops-206240}, doi = {10.4230/LIPIcs.MFCS.2024.68}, annote = {Keywords: hitting set, line-constrained, line-separable, unit disks, half-planes, coverage} }
Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
Gang Liu and Haitao Wang. On Line-Separable Weighted Unit-Disk Coverage and Related Problems. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 70:1-70:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{liu_et_al:LIPIcs.MFCS.2024.70, author = {Liu, Gang and Wang, Haitao}, title = {{On Line-Separable Weighted Unit-Disk Coverage and Related Problems}}, booktitle = {49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)}, pages = {70:1--70:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-335-5}, ISSN = {1868-8969}, year = {2024}, volume = {306}, editor = {Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.70}, URN = {urn:nbn:de:0030-drops-206265}, doi = {10.4230/LIPIcs.MFCS.2024.70}, annote = {Keywords: Line-separable, unit disks, halfplanes, geometric coverage, geometric hitting set} }
Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)
Nick Krumbholz, Stefan Funke, Peter Schäfer, and Sabine Storandt. Algorithms for Gradual Polyline Simplification. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 19:1-19:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{krumbholz_et_al:LIPIcs.SEA.2024.19, author = {Krumbholz, Nick and Funke, Stefan and Sch\"{a}fer, Peter and Storandt, Sabine}, title = {{Algorithms for Gradual Polyline Simplification}}, booktitle = {22nd International Symposium on Experimental Algorithms (SEA 2024)}, pages = {19:1--19:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-325-6}, ISSN = {1868-8969}, year = {2024}, volume = {301}, editor = {Liberti, Leo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.19}, URN = {urn:nbn:de:0030-drops-203847}, doi = {10.4230/LIPIcs.SEA.2024.19}, annote = {Keywords: Polyline simplification, Progressive simplification, Fr\'{e}chet distance} }
Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)
Patrick Dinklage, Johannes Fischer, and Nicola Prezza. Top-k Frequent Patterns in Streams and Parameterized-Space LZ Compression. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 9:1-9:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{dinklage_et_al:LIPIcs.SEA.2024.9, author = {Dinklage, Patrick and Fischer, Johannes and Prezza, Nicola}, title = {{Top-k Frequent Patterns in Streams and Parameterized-Space LZ Compression}}, booktitle = {22nd International Symposium on Experimental Algorithms (SEA 2024)}, pages = {9:1--9:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-325-6}, ISSN = {1868-8969}, year = {2024}, volume = {301}, editor = {Liberti, Leo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.9}, URN = {urn:nbn:de:0030-drops-203748}, doi = {10.4230/LIPIcs.SEA.2024.9}, annote = {Keywords: compression, streaming, heavy hitters, algorithm engineering} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Greg Bodwin, Chengyuan Deng, Jie Gao, Gary Hoppenworth, Jalaj Upadhyay, and Chen Wang. The Discrepancy of Shortest Paths. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 27:1-27:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bodwin_et_al:LIPIcs.ICALP.2024.27, author = {Bodwin, Greg and Deng, Chengyuan and Gao, Jie and Hoppenworth, Gary and Upadhyay, Jalaj and Wang, Chen}, title = {{The Discrepancy of Shortest Paths}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {27:1--27:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.27}, URN = {urn:nbn:de:0030-drops-201705}, doi = {10.4230/LIPIcs.ICALP.2024.27}, annote = {Keywords: Discrepancy, hereditary discrepancy, shortest paths, differential privacy} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Itai Boneh, Shay Golan, Shay Mozes, and Oren Weimann. Õptimal Dynamic Time Warping on Run-Length Encoded Strings. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 30:1-30:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{boneh_et_al:LIPIcs.ICALP.2024.30, author = {Boneh, Itai and Golan, Shay and Mozes, Shay and Weimann, Oren}, title = {{\~{O}ptimal Dynamic Time Warping on Run-Length Encoded Strings}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {30:1--30:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.30}, URN = {urn:nbn:de:0030-drops-201730}, doi = {10.4230/LIPIcs.ICALP.2024.30}, annote = {Keywords: Dynamic time warping, Fr\'{e}chet distance, edit distance, run-length encoding} }
Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)
Pankaj K. Agarwal, Esther Ezra, and Micha Sharir. Semi-Algebraic Off-Line Range Searching and Biclique Partitions in the Plane. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{agarwal_et_al:LIPIcs.SoCG.2024.4, author = {Agarwal, Pankaj K. and Ezra, Esther and Sharir, Micha}, title = {{Semi-Algebraic Off-Line Range Searching and Biclique Partitions in the Plane}}, booktitle = {40th International Symposium on Computational Geometry (SoCG 2024)}, pages = {4:1--4:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-316-4}, ISSN = {1868-8969}, year = {2024}, volume = {293}, editor = {Mulzer, Wolfgang and Phillips, Jeff M.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.4}, URN = {urn:nbn:de:0030-drops-199497}, doi = {10.4230/LIPIcs.SoCG.2024.4}, annote = {Keywords: Range-searching, semi-algebraic sets, pseudo-lines, duality, geometric cuttings} }
Published in: LIPIcs, Volume 290, 27th International Conference on Database Theory (ICDT 2024)
Pankaj K. Agarwal, Rahul Raychaudhury, Stavros Sintos, and Jun Yang. Computing Data Distribution from Query Selectivities. In 27th International Conference on Database Theory (ICDT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 290, pp. 18:1-18:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{agarwal_et_al:LIPIcs.ICDT.2024.18, author = {Agarwal, Pankaj K. and Raychaudhury, Rahul and Sintos, Stavros and Yang, Jun}, title = {{Computing Data Distribution from Query Selectivities}}, booktitle = {27th International Conference on Database Theory (ICDT 2024)}, pages = {18:1--18:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-312-6}, ISSN = {1868-8969}, year = {2024}, volume = {290}, editor = {Cormode, Graham and Shekelyan, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2024.18}, URN = {urn:nbn:de:0030-drops-198007}, doi = {10.4230/LIPIcs.ICDT.2024.18}, annote = {Keywords: selectivity queries, discrete distributions, Multiplicative Weights Update, eps-approximation, learnable functions, depth problem, arrangement} }
Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Morteza Monemizadeh. Facility Location in the Sublinear Geometric Model. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 6:1-6:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{monemizadeh:LIPIcs.APPROX/RANDOM.2023.6, author = {Monemizadeh, Morteza}, title = {{Facility Location in the Sublinear Geometric Model}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {6:1--6:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-296-9}, ISSN = {1868-8969}, year = {2023}, volume = {275}, editor = {Megow, Nicole and Smith, Adam}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.6}, URN = {urn:nbn:de:0030-drops-188315}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.6}, annote = {Keywords: Facility Location, Sublinear Geometric Model, Range Counting Queries} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Peyman Afshani, Pingan Cheng, Aniket Basu Roy, and Zhewei Wei. On Range Summary Queries. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{afshani_et_al:LIPIcs.ICALP.2023.7, author = {Afshani, Peyman and Cheng, Pingan and Basu Roy, Aniket and Wei, Zhewei}, title = {{On Range Summary Queries}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {7:1--7:17}, 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.7}, URN = {urn:nbn:de:0030-drops-180590}, doi = {10.4230/LIPIcs.ICALP.2023.7}, annote = {Keywords: Computational Geometry, Range Searching, Random Sampling, Geometric Approximation, Data Structures and Algorithms} }
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 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
Pankaj K. Agarwal, Tzvika Geft, Dan Halperin, and Erin Taylor. Multi-Robot Motion Planning for Unit Discs with Revolving Areas. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 35:1-35:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{agarwal_et_al:LIPIcs.ISAAC.2022.35, author = {Agarwal, Pankaj K. and Geft, Tzvika and Halperin, Dan and Taylor, Erin}, title = {{Multi-Robot Motion Planning for Unit Discs with Revolving Areas}}, booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)}, pages = {35:1--35:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-258-7}, ISSN = {1868-8969}, year = {2022}, volume = {248}, editor = {Bae, Sang Won and Park, Heejin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.35}, URN = {urn:nbn:de:0030-drops-173204}, doi = {10.4230/LIPIcs.ISAAC.2022.35}, annote = {Keywords: motion planning, optimal motion planning, approximation, complexity, NP-hardness} }
Feedback for Dagstuhl Publishing