Search Results

Documents authored by Seybold, Martin P.

Document
DOI: 10.4230/LIPIcs.SoCG.2024.62
Approximating Multiplicatively Weighted Voronoi Diagrams: Efficient Construction with Linear Size

Authors: Joachim Gudmundsson, Martin P. Seybold, and Sampson Wong

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
Given a set of n sites from ℝ^d, each having some positive weight factor, the Multiplicatively Weighted Voronoi Diagram is a subdivision of space that associates each cell to the site whose weighted Euclidean distance is minimal for all points in the cell. We give novel approximation algorithms that output a cube-based subdivision such that the weighted distance of a point with respect to the associated site is at most (1+ε) times the minimum weighted distance, for any fixed parameter ε ∈ (0,1). The diagram size is O_d(n log(1/ε)/ε^{d-1}) and the construction time is within an O_D(log(n)/ε^{(d+5)/2})-factor of the size bound. We also prove a matching lower bound for the size, showing that the proposed method is the first to achieve optimal size, up to Θ(1)^d-factors. In particular, the obscure log(1/ε) factor is unavoidable. As a by-product, we obtain a factor d^{O(d)} improvement in size for the unweighted case and O(d log(n) + d² log(1/ε)) point-location time in the subdivision, improving the known query bound by one d-factor. The key ingredients of our approximation algorithms are the study of convex regions that we call cores, an adaptive refinement algorithm to obtain optimal size, and a novel notion of bisector coresets, which may be of independent interest. In particular, we show that coresets with O_d(1/ε^{(d+3)/2}) worst-case size can be computed in near-linear time.
Cite as

Joachim Gudmundsson, Martin P. Seybold, and Sampson Wong. Approximating Multiplicatively Weighted Voronoi Diagrams: Efficient Construction with Linear Size. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 62:1-62:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gudmundsson_et_al:LIPIcs.SoCG.2024.62,
  author =	{Gudmundsson, Joachim and Seybold, Martin P. and Wong, Sampson},
  title =	{{Approximating Multiplicatively Weighted Voronoi Diagrams: Efficient Construction with Linear Size}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{62:1--62:14},
  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.62},
  URN =		{urn:nbn:de:0030-drops-200078},
  doi =		{10.4230/LIPIcs.SoCG.2024.62},
  annote =	{Keywords: Multiplicatively Weighted Voronoi Diagram, Compressed QuadTree, Adaptive Refinement, Bisector Coresets, Semi-Separated Pair Decomposition, Lower Bound}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2024.62
On the Complexity of Algorithms with Predictions for Dynamic Graph Problems

Authors: Monika Henzinger, Barna Saha, Martin P. Seybold, and Christopher Ye

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
Algorithms with predictions is a new research direction that leverages machine learned predictions for algorithm design. So far a plethora of recent works have incorporated predictions to improve on worst-case bounds for online problems. In this paper, we initiate the study of complexity of dynamic data structures with predictions, including dynamic graph algorithms. Unlike online algorithms, the goal in dynamic data structures is to maintain the solution efficiently with every update. We investigate three natural models of prediction: (1) δ-accurate predictions where each predicted request matches the true request with probability δ, (2) list-accurate predictions where a true request comes from a list of possible requests, and (3) bounded delay predictions where the true requests are a permutation of the predicted requests. We give general reductions among the prediction models, showing that bounded delay is the strongest prediction model, followed by list-accurate, and δ-accurate. Further, we identify two broad problem classes based on lower bounds due to the Online Matrix Vector (OMv) conjecture. Specifically, we show that locally correctable dynamic problems have strong conditional lower bounds for list-accurate predictions that are equivalent to the non-prediction setting, unless list-accurate predictions are perfect. Moreover, we show that locally reducible dynamic problems have time complexity that degrades gracefully with the quality of bounded delay predictions. We categorize problems with known OMv lower bounds accordingly and give several upper bounds in the delay model that show that our lower bounds are almost tight. We note that concurrent work by v.d.Brand et al. [SODA '24] and Liu and Srinivas [arXiv:2307.08890] independently study dynamic graph algorithms with predictions, but their work is mostly focused on showing upper bounds.
Cite as

Monika Henzinger, Barna Saha, Martin P. Seybold, and Christopher Ye. On the Complexity of Algorithms with Predictions for Dynamic Graph Problems. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 62:1-62:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{henzinger_et_al:LIPIcs.ITCS.2024.62,
  author =	{Henzinger, Monika and Saha, Barna and Seybold, Martin P. and Ye, Christopher},
  title =	{{On the Complexity of Algorithms with Predictions for Dynamic Graph Problems}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{62:1--62:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.62},
  URN =		{urn:nbn:de:0030-drops-195907},
  doi =		{10.4230/LIPIcs.ITCS.2024.62},
  annote =	{Keywords: Dynamic Graph Algorithms, Algorithms with Predictions}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.18
A Simple Dynamization of Trapezoidal Point Location in Planar Subdivisions

Authors: Milutin Brankovic, Nikola Grujic, André van Renssen, and Martin P. Seybold

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
We study how to dynamize the Trapezoidal Search Tree (TST) - a well known randomized point location structure for planar subdivisions of kinetic line segments. Our approach naturally extends incremental leaf-level insertions to recursive methods and allows adaptation for the online setting. The dynamization carries over to the Trapezoidal Search DAG (TSD), which has linear size and logarithmic point location costs with high probability. On a set S of non-crossing segments, each TST update performs expected 𝒪(log²|S|) operations and each TSD update performs expected 𝒪(log |S|) operations. We demonstrate the practicality of our method with an open-source implementation, based on the Computational Geometry Algorithms Library, and experiments on the update performance.
Cite as

Milutin Brankovic, Nikola Grujic, André van Renssen, and Martin P. Seybold. A Simple Dynamization of Trapezoidal Point Location in Planar Subdivisions. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 18:1-18:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{brankovic_et_al:LIPIcs.ICALP.2020.18,
  author =	{Brankovic, Milutin and Grujic, Nikola and van Renssen, Andr\'{e} and Seybold, Martin P.},
  title =	{{A Simple Dynamization of Trapezoidal Point Location in Planar Subdivisions}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{18:1--18:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.18},
  URN =		{urn:nbn:de:0030-drops-124253},
  doi =		{10.4230/LIPIcs.ICALP.2020.18},
  annote =	{Keywords: Dynamization, Trapezoidal Search Tree, Trapezoidal Search DAG, Backward Analysis, Point Location, Planar Subdivision, Treap, Order-maintenance}
}
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact