Search Results

Documents authored by de Berg, Sarita

Document
DOI: 10.4230/LIPIcs.ESA.2026.52
A Dynamic (1+ε)-Spanner for Disk Intersection Graphs

Authors: Sarita de Berg, Ivor van der Hoog, Eva Rotenberg, Johanne Müller Vistisen, and Sampson Wong

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract
We maintain a (1+ε)-spanner over the disk intersection graph of a dynamic set of disks. We restrict all disks to have their diameter in [4,Ψ] for some fixed and known Ψ. The resulting (1+ε)-spanner has size O(n ε^{-2} log Ψ log(ε^{-1})), where n is the present number of disks. We develop a novel use of persistent data structures to dynamically maintain our (1+ε)-spanner. Our approach requires O(ε^{-2} n log⁴n log Ψ) space and has an O((Ψ/ε)² log⁴n log²Ψ log²(ε^{-1})) expected amortised update time. For constant ε and Ψ, this spanner has near-linear size, uses near-linear space and has polylogarithmic update time. Furthermore, we observe that for any ε < 1, our spanner also serves as a connectivity data structure. With a slight adaptation of our techniques, this leads to better bounds for dynamically supporting connectivity queries in a disk intersection graph. In particular, we improve the space usage when compared to the dynamic data structure of (Baumann et al., DCG'24), replacing the linear dependency on Ψ by a polylogarithmic dependency. Finally, we generalise our results to d-dimensional hypercubes.
Cite as

Sarita de Berg, Ivor van der Hoog, Eva Rotenberg, Johanne Müller Vistisen, and Sampson Wong. A Dynamic (1+ε)-Spanner for Disk Intersection Graphs. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 52:1-52:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{deberg_et_al:LIPIcs.ESA.2026.52,
  author =	{de Berg, Sarita and van der Hoog, Ivor and Rotenberg, Eva and Vistisen, Johanne M\"{u}ller and Wong, Sampson},
  title =	{{A Dynamic (1+\epsilon)-Spanner for Disk Intersection Graphs}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{52:1--52:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.52},
  URN =		{urn:nbn:de:0030-drops-271880},
  doi =		{10.4230/LIPIcs.ESA.2026.52},
  annote =	{Keywords: intersection graphs, dynamic data structures, spanners}
}
Document
DOI: 10.4230/LIPIcs.ESA.2026.106
Instance Optimal and Universally Optimal Bounds for Imprecise Pareto Fronts

Authors: Sarita de Berg, Nynne Maria Foldager Bække, Frida Astrup Eriksen, Ivor van der Hoog, Eva Rotenberg, and Daniel Rutschmann

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract
In the imprecise geometry model, the input is a family of regions F = (R₁, R₂, …,R_n), each containing a point p_i ∈ R_i. The task is then to compute some function of the points p₁,p₂,… p_n, in our case an implicit representation of their Pareto front. To this end, one may query a region R_i to retrieve its contained point p_i ∈ R_i. In this model, efficiency is interpreted in two ways: minimizing (i) the number of retrievals, and (ii) the computation time both for preprocessing, and the execution of the query stage, i.e. for computing which points to query and constructing the output. We present an algorithm to construct (an implicit representation of) the Pareto front for possibly overlapping rectangles, that is instance-optimal with respect to the number of retrievals. This means that for every fixed input (F, P), there is no algorithm that retrieves asymptotically fewer regions to compute the output. This is a strong algorithmic quality, as it means that our algorithm is competitive even to clairvoyant algorithms which only have to verify the correctness of a correct guess. In terms of algorithmic running time, instance-optimality is provably unobtainable. We instead present an algorithm which is within a log n-factor of instance optimality. This generalizes earlier results which assumed the regions to not overlap, at only a minor cost in running time. For unit squares, we present an algorithm that is not only instance optimal in the number of retrievals, but also universally optimal in terms of running time. This means that for any fixed set of regions F, no algorithm has a better worst-case running time for all possible point sets P. Thus, this work presents the first universally optimal algorithm for overlapping planar input. Compared to previous work, our result improves the degree to which the input regions may overlap, the preprocessing time, the number of retrievals, and the running time.
Cite as

Sarita de Berg, Nynne Maria Foldager Bække, Frida Astrup Eriksen, Ivor van der Hoog, Eva Rotenberg, and Daniel Rutschmann. Instance Optimal and Universally Optimal Bounds for Imprecise Pareto Fronts. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 106:1-106:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{deberg_et_al:LIPIcs.ESA.2026.106,
  author =	{de Berg, Sarita and B{\ae}kke, Nynne Maria Foldager and Eriksen, Frida Astrup and van der Hoog, Ivor and Rotenberg, Eva and Rutschmann, Daniel},
  title =	{{Instance Optimal and Universally Optimal Bounds for Imprecise Pareto Fronts}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{106:1--106:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.106},
  URN =		{urn:nbn:de:0030-drops-272426},
  doi =		{10.4230/LIPIcs.ESA.2026.106},
  annote =	{Keywords: Pareto front, imprecise geometry, instance optimality, universal optimality, preprocessing model, partial information}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.25
Instance-Optimal Imprecise Convex Hull

Authors: Sarita de Berg, Ivor van der Hoog, Eva Rotenberg, Daniel Rutschmann, and Sampson Wong

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
Imprecise measurements of a point set P = (p₁, …, p_n) can be modelled by a family of regions F = (R₁, …, R_n), where each imprecise region R_i ∈ F contains a unique point p_i ∈ P. A retrieval models an accurate measurement by replacing an imprecise region R_i with its corresponding point p_i. We construct the convex hull of an imprecise point set in the plane, by determining the cyclic ordering of the convex hull vertices of P as efficiently as possible. Efficiency is interpreted in two ways: (i) minimising the number of retrievals, and (ii) the computation time to determine the set of regions that must be retrieved. Previous works focused on only one of these two aspects: either minimising retrievals or optimising algorithmic runtime. Our contribution is the first to simultaneously achieve both. Let r(F, P) denote the minimal number of retrievals required by any algorithm to determine the convex hull of P for a given instance (F, P). For a family F of n constant-complexity polygons, our main result is a reconstruction algorithm that performs Θ(r(F, P)) retrievals in O(r(F, P) log³ n) time. Compared to previous approaches that achieve optimal retrieval counts, we improve the runtime per retrieval from polynomial to polylogarithmic. We extend the generality of previous results to simple k-gons, to pairwise disjoint disks with radii in [1,k], and to unit disks where at most k disks overlap in a single point. Our runtime scales linearly with k.
Cite as

Sarita de Berg, Ivor van der Hoog, Eva Rotenberg, Daniel Rutschmann, and Sampson Wong. Instance-Optimal Imprecise Convex Hull. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 25:1-25:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{deberg_et_al:LIPIcs.ESA.2025.25,
  author =	{de Berg, Sarita and van der Hoog, Ivor and Rotenberg, Eva and Rutschmann, Daniel and Wong, Sampson},
  title =	{{Instance-Optimal Imprecise Convex Hull}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{25:1--25:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian 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.2025.25},
  URN =		{urn:nbn:de:0030-drops-244932},
  doi =		{10.4230/LIPIcs.ESA.2025.25},
  annote =	{Keywords: convex hull, imprecise geometry preprocessing model, partial information}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.37
Nearest Neighbor Searching in a Dynamic Simple Polygon

Authors: Sarita de Berg and Frank Staals

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
In the nearest neighbor problem, we are given a set S of point sites that we want to store such that we can find the nearest neighbor of a (new) query point efficiently. In the dynamic version of the problem, the goal is to design a data structure that supports both efficient queries and updates, i.e. insertions and deletions in S. This problem has been widely studied in various settings, ranging from points in the plane to more general distance measures and even points within simple polygons. When the sites do not live in the plane but in some domain, another dynamic problem arises: what happens if not the sites, but the domain itself is subject to updates? Updating sites often results in local changes to the solution or data structure, while updating the domain may incur many global changes. For example, in the closest pair problem, inserting a point only requires us to check if this point is in the new closest pair, while updating the domain might change the distances between most pairs of points in our set. Presumably, this is the reason that this form of dynamization has received much less attention. Only some basic problems, such as shortest paths and ray shooting, have been studied in this setting. Here, we tackle the nearest neighbor problem in a dynamic simple polygon. We allow insertions into both the set of sites and the polygon. An insertion in the polygon is the addition of a line segment starting at the boundary of the polygon. We present a near-linear size -in both the number of sites and the complexity of the polygon- data structure with sublinear update and query time. This is the first nearest neighbor data structure that allows for updates to the domain.
Cite as

Sarita de Berg and Frank Staals. Nearest Neighbor Searching in a Dynamic Simple Polygon. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 37:1-37:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{deberg_et_al:LIPIcs.SoCG.2025.37,
  author =	{de Berg, Sarita and Staals, Frank},
  title =	{{Nearest Neighbor Searching in a Dynamic Simple Polygon}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{37:1--37:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.37},
  URN =		{urn:nbn:de:0030-drops-231896},
  doi =		{10.4230/LIPIcs.SoCG.2025.37},
  annote =	{Keywords: dynamic data structure, simple polygon, geodesic distance, nearest neighbor}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2024.25
The Complexity of Geodesic Spanners Using Steiner Points

Authors: Sarita de Berg, Tim Ophelders, Irene Parada, Frank Staals, and Jules Wulms

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
A geometric t-spanner 𝒢 on a set S of n point sites in a metric space P is a subgraph of the complete graph on S such that for every pair of sites p,q the distance in 𝒢 is a most t times the distance d(p,q) in P. We call a connection between two sites a link. In some settings, such as when P is a simple polygon with m vertices and a link is a shortest path in P, links can consist of Θ (m) segments and thus have non-constant complexity. The spanner complexity is a measure of how compact a spanner is, which is equal to the sum of the complexities of all links in the spanner. In this paper, we study what happens if we are allowed to introduce k Steiner points to reduce the spanner complexity. We study such Steiner spanners in simple polygons, polygonal domains, and edge-weighted trees. Surprisingly, we show that Steiner points have only limited utility. For a spanner that uses k Steiner points, we provide an Ω(nm/k) lower bound on the worst-case complexity of any (3-ε)-spanner, and an Ω(mn^{1/(t+1)}/k^{1/(t+1)}) lower bound on the worst-case complexity of any (t-ε)-spanner, for any constant ε ∈ (0,1) and integer constant t ≥ 2. These lower bounds hold in all settings. Additionally, we show NP-hardness for the problem of deciding whether a set of sites in a polygonal domain admits a 3-spanner with a given maximum complexity using k Steiner points. On the positive side, for trees we show how to build a 2t-spanner that uses k Steiner points of complexity O(mn^{1/t}/k^{1/t} + n log (n/k)), for any integer t ≥ 1. We generalize this result to forests, and apply it to obtain a 2√2t-spanner in a simple polygon with total complexity O(mn^{1/t}(log k)^{1+1/t}/k^{1/t} + nlog² n). When a link in the spanner can be any path between two sites, we show how to improve the spanning ratio in a simple polygon to (2k+ε), for any constant ε ∈ (0,2k), and how to build a 6t-spanner in a polygonal domain with the same complexity.
Cite as

Sarita de Berg, Tim Ophelders, Irene Parada, Frank Staals, and Jules Wulms. The Complexity of Geodesic Spanners Using Steiner Points. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 25:1-25:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{deberg_et_al:LIPIcs.ISAAC.2024.25,
  author =	{de Berg, Sarita and Ophelders, Tim and Parada, Irene and Staals, Frank and Wulms, Jules},
  title =	{{The Complexity of Geodesic Spanners Using Steiner Points}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{25:1--25:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.25},
  URN =		{urn:nbn:de:0030-drops-221527},
  doi =		{10.4230/LIPIcs.ISAAC.2024.25},
  annote =	{Keywords: spanner, simple polygon, polygonal domain, geodesic distance, complexity}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2024.2
Clustering with Few Disks to Minimize the Sum of Radii

Authors: Mikkel Abrahamsen, Sarita de Berg, Lucas Meijer, André Nusser, and Leonidas Theocharous

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

Abstract
Given a set of n points in the Euclidean plane, the k-MinSumRadius problem asks to cover this point set using k disks with the objective of minimizing the sum of the radii of the disks. After a long line of research on related problems, it was finally discovered that this problem admits a polynomial time algorithm [GKKPV '12]; however, the running time of this algorithm is 𝒪(n^881), and its relevance is thereby mostly of theoretical nature. A practically and structurally interesting special case of the k-MinSumRadius problem is that of small k. For the 2-MinSumRadius problem, a near-quadratic time algorithm with expected running time 𝒪(n² log² n log² log n) was given over 30 years ago [Eppstein '92]. We present the first improvement of this result, namely, a near-linear time algorithm to compute the 2-MinSumRadius that runs in expected 𝒪(n log² n log² log n) time. We generalize this result to any constant dimension d, for which we give an 𝒪(n^{2-1/(⌈d/2⌉ + 1) + ε}) time algorithm. Additionally, we give a near-quadratic time algorithm for 3-MinSumRadius in the plane that runs in expected 𝒪(n² log² n log² log n) time. All of these algorithms rely on insights that uncover a surprisingly simple structure of optimal solutions: we can specify a linear number of lines out of which one separates one of the clusters from the remaining clusters in an optimal solution.
Cite as

Mikkel Abrahamsen, Sarita de Berg, Lucas Meijer, André Nusser, and Leonidas Theocharous. Clustering with Few Disks to Minimize the Sum of Radii. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 2:1-2:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{abrahamsen_et_al:LIPIcs.SoCG.2024.2,
  author =	{Abrahamsen, Mikkel and de Berg, Sarita and Meijer, Lucas and Nusser, Andr\'{e} and Theocharous, Leonidas},
  title =	{{Clustering with Few Disks to Minimize the Sum of Radii}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{2:1--2: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.2},
  URN =		{urn:nbn:de:0030-drops-199472},
  doi =		{10.4230/LIPIcs.SoCG.2024.2},
  annote =	{Keywords: geometric clustering, minimize sum of radii, covering points with disks}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2024.17
Towards Space Efficient Two-Point Shortest Path Queries in a Polygonal Domain

Authors: Sarita de Berg, Tillmann Miltzow, and Frank Staals

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

Abstract
We devise a data structure that can answer shortest path queries for two query points in a polygonal domain P on n vertices. For any ε > 0, the space complexity of the data structure is O(n^{10+ε}) and queries can be answered in O(log n) time. Alternatively, we can achieve a space complexity of O(n^{9+ε}) by relaxing the query time to O(log² n). This is the first improvement upon a conference paper by Chiang and Mitchell from 1999. They presented a data structure with O(n^{11}) space complexity and O(log n) query time. Our main result can be extended to include a space-time trade-off. Specifically, we devise data structures with O(n^{9+ε}/𝓁^{4+O(ε)}) space complexity and O(𝓁 log² n) query time, for any integer 1 ≤ 𝓁 ≤ n. Furthermore, we present improved data structures for the special case where we restrict one (or both) of the query points to lie on the boundary of P. When one of the query points is restricted to lie on the boundary, and the other query point is unrestricted, the space complexity becomes O(n^{6+ε}) and the query time O(log²n). When both query points are on the boundary, the space complexity is decreased further to O(n^{4+ε}) and the query time to O(log n), thereby improving an earlier result of Bae and Okamoto.
Cite as

Sarita de Berg, Tillmann Miltzow, and Frank Staals. Towards Space Efficient Two-Point Shortest Path Queries in a Polygonal Domain. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 17:1-17:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{deberg_et_al:LIPIcs.SoCG.2024.17,
  author =	{de Berg, Sarita and Miltzow, Tillmann and Staals, Frank},
  title =	{{Towards Space Efficient Two-Point Shortest Path Queries in a Polygonal Domain}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{17:1--17:16},
  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.17},
  URN =		{urn:nbn:de:0030-drops-199628},
  doi =		{10.4230/LIPIcs.SoCG.2024.17},
  annote =	{Keywords: data structure, polygonal domain, geodesic distance}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.16
The Complexity of Geodesic Spanners

Authors: Sarita de Berg, Marc van Kreveld, and Frank Staals

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
A geometric t-spanner for a set S of n point sites is an edge-weighted graph for which the (weighted) distance between any two sites p,q ∈ S is at most t times the original distance between p and q. We study geometric t-spanners for point sets in a constrained two-dimensional environment P. In such cases, the edges of the spanner may have non-constant complexity. Hence, we introduce a novel spanner property: the spanner complexity, that is, the total complexity of all edges in the spanner. Let S be a set of n point sites in a simple polygon P with m vertices. We present an algorithm to construct, for any constant ε > 0 and fixed integer k ≥ 1, a (2k + ε)-spanner with complexity O(mn^{1/k} + nlog² n) in O(nlog²n + mlog n + K) time, where K denotes the output complexity. When we consider sites in a polygonal domain P with holes, we can construct such a (2k+ε)-spanner of similar complexity in O(n² log m + nmlog m + K) time. Additionally, for any constant ε ∈ (0,1) and integer constant t ≥ 2, we show a lower bound for the complexity of any (t-ε)-spanner of Ω(mn^{1/(t-1)} + n).
Cite as

Sarita de Berg, Marc van Kreveld, and Frank Staals. The Complexity of Geodesic Spanners. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 16:1-16:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{deberg_et_al:LIPIcs.SoCG.2023.16,
  author =	{de Berg, Sarita and van Kreveld, Marc and Staals, Frank},
  title =	{{The Complexity of Geodesic Spanners}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{16:1--16: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.16},
  URN =		{urn:nbn:de:0030-drops-178669},
  doi =		{10.4230/LIPIcs.SoCG.2023.16},
  annote =	{Keywords: spanner, simple polygon, polygonal domain, geodesic distance, complexity}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.14
Dynamic Data Structures for k-Nearest Neighbor Queries

Authors: Sarita de Berg and Frank Staals

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
Our aim is to develop dynamic data structures that support k-nearest neighbors (k-NN) queries for a set of n point sites in O(f(n) + k) time, where f(n) is some polylogarithmic function of n. The key component is a general query algorithm that allows us to find the k-NN spread over t substructures simultaneously, thus reducing a O(tk) term in the query time to O(k). Combining this technique with the logarithmic method allows us to turn any static k-NN data structure into a data structure supporting both efficient insertions and queries. For the fully dynamic case, this technique allows us to recover the deterministic, worst-case, O(log²n/log log n +k) query time for the Euclidean distance claimed before, while preserving the polylogarithmic update times. We adapt this data structure to also support fully dynamic geodesic k-NN queries among a set of sites in a simple polygon. For this purpose, we design a shallow cutting based, deletion-only k-NN data structure. More generally, we obtain a dynamic k-NN data structure for any type of distance functions for which we can build vertical shallow cuttings. We apply all of our methods in the plane for the Euclidean distance, the geodesic distance, and general, constant-complexity, algebraic distance functions.
Cite as

Sarita de Berg and Frank Staals. Dynamic Data Structures for k-Nearest Neighbor Queries. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{deberg_et_al:LIPIcs.ISAAC.2021.14,
  author =	{de Berg, Sarita and Staals, Frank},
  title =	{{Dynamic Data Structures for k-Nearest Neighbor Queries}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{14:1--14:14},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.14},
  URN =		{urn:nbn:de:0030-drops-154473},
  doi =		{10.4230/LIPIcs.ISAAC.2021.14},
  annote =	{Keywords: data structure, simple polygon, geodesic distance, nearest neighbor searching}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact