Search Results

Documents authored by Staals, Frank

Document
DOI: 10.4230/LIPIcs.MFCS.2024.63
Fully-Adaptive Dynamic Connectivity of Square Intersection Graphs

Authors: Ivor van der Hoog, André Nusser, Eva Rotenberg, and Frank Staals

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
A classical problem in computational geometry and graph algorithms is: given a dynamic set 𝒮 of geometric shapes in the plane, efficiently maintain the connectivity of the intersection graph of 𝒮. Previous papers studied the setting where, before the updates, the data structure receives some parameter P. Then, updates could insert and delete disks as long as at all times the disks have a diameter that lies in a fixed range [1/P, 1]. As a consequence of that prerequisite, the aspect ratio ψ (i.e. the ratio between the largest and smallest diameter) of the disks would at all times satisfy ψ ≤ P. The state-of-the-art for storing disks in a dynamic connectivity data structure is a data structure that uses O(Pn) space and that has amortized O(P log⁴ n) expected amortized update time. Connectivity queries between disks are supported in O(log n / log log n) time. In the dynamic setting, one wishes for a more flexible data structure in which disks of any diameter may arrive and leave, independent of their diameter, changing the aspect ratio freely. Ideally, the aspect ratio should merely be part of the analysis. We restrict our attention to axis-aligned squares, and study fully-dynamic square intersection graph connectivity. Our result is fully-adaptive to the aspect ratio, spending time proportional to the current aspect ratio ψ, as opposed to some previously given maximum P. Our focus on squares allows us to simplify and streamline the connectivity pipeline from previous work. When n is the number of squares and ψ is the aspect ratio after insertion (or before deletion), our data structure answers connectivity queries in O(log n / log log n) time. We can update connectivity information in O(ψ log⁴ n + log⁶ n) amortized time. We also improve space usage from O(P ⋅ n log n) to O(n log³ n log ψ) - while generalizing to a fully-adaptive aspect ratio - which yields a space usage that is near-linear in n for any polynomially bounded ψ.
Cite as

Ivor van der Hoog, André Nusser, Eva Rotenberg, and Frank Staals. Fully-Adaptive Dynamic Connectivity of Square Intersection Graphs. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 63:1-63:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{vanderhoog_et_al:LIPIcs.MFCS.2024.63,
  author =	{van der Hoog, Ivor and Nusser, Andr\'{e} and Rotenberg, Eva and Staals, Frank},
  title =	{{Fully-Adaptive Dynamic Connectivity of Square Intersection Graphs}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{63:1--63:17},
  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.63},
  URN =		{urn:nbn:de:0030-drops-206197},
  doi =		{10.4230/LIPIcs.MFCS.2024.63},
  annote =	{Keywords: Computational geometry, planar geometry, data structures, geometric intersection graphs, fully-dynamic algorithms}
}
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.2024.25
Fine-Grained Complexity of Earth Mover’s Distance Under Translation

Authors: Karl Bringmann, Frank Staals, Karol Węgrzycki, and Geert van Wordragen

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

Abstract
The Earth Mover’s Distance is a popular similarity measure in several branches of computer science. It measures the minimum total edge length of a perfect matching between two point sets. The Earth Mover’s Distance under Translation (EMDuT) is a translation-invariant version thereof. It minimizes the Earth Mover’s Distance over all translations of one point set. For EMDuT in ℝ¹, we present an 𝒪̃(n²)-time algorithm. We also show that this algorithm is nearly optimal by presenting a matching conditional lower bound based on the Orthogonal Vectors Hypothesis. For EMDuT in ℝ^d, we present an 𝒪̃(n^{2d+2})-time algorithm for the L₁ and L_∞ metric. We show that this dependence on d is asymptotically tight, as an n^o(d)-time algorithm for L_1 or L_∞ would contradict the Exponential Time Hypothesis (ETH). Prior to our work, only approximation algorithms were known for these problems.
Cite as

Karl Bringmann, Frank Staals, Karol Węgrzycki, and Geert van Wordragen. Fine-Grained Complexity of Earth Mover’s Distance Under Translation. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bringmann_et_al:LIPIcs.SoCG.2024.25,
  author =	{Bringmann, Karl and Staals, Frank and W\k{e}grzycki, Karol and van Wordragen, Geert},
  title =	{{Fine-Grained Complexity of Earth Mover’s Distance Under Translation}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{25:1--25:17},
  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.25},
  URN =		{urn:nbn:de:0030-drops-199706},
  doi =		{10.4230/LIPIcs.SoCG.2024.25},
  annote =	{Keywords: Earth Mover’s Distance, Earth Mover’s Distance under Translation, Fine-Grained Complexity, Maximum Weight Bipartite Matching}
}
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.SoCG.2023.48
Shortest Paths in Portalgons

Authors: Maarten Löffler, Tim Ophelders, Rodrigo I. Silveira, and Frank Staals

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

Abstract
Any surface that is intrinsically polyhedral can be represented by a collection of simple polygons (fragments), glued along pairs of equally long oriented edges, where each fragment is endowed with the geodesic metric arising from its Euclidean metric. We refer to such a representation as a portalgon, and we call two portalgons equivalent if the surfaces they represent are isometric. We analyze the complexity of shortest paths. We call a fragment happy if any shortest path on the portalgon visits it at most a constant number of times. A portalgon is happy if all of its fragments are happy. We present an efficient algorithm to compute shortest paths on happy portalgons. The number of times that a shortest path visits a fragment is unbounded in general. We contrast this by showing that the intrinsic Delaunay triangulation of any polyhedral surface corresponds to a happy portalgon. Since computing the intrinsic Delaunay triangulation may be inefficient, we provide an efficient algorithm to compute happy portalgons for a restricted class of portalgons.
Cite as

Maarten Löffler, Tim Ophelders, Rodrigo I. Silveira, and Frank Staals. Shortest Paths in Portalgons. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 48:1-48:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{loffler_et_al:LIPIcs.SoCG.2023.48,
  author =	{L\"{o}ffler, Maarten and Ophelders, Tim and Silveira, Rodrigo I. and Staals, Frank},
  title =	{{Shortest Paths in Portalgons}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{48:1--48: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.48},
  URN =		{urn:nbn:de:0030-drops-178980},
  doi =		{10.4230/LIPIcs.SoCG.2023.48},
  annote =	{Keywords: Polyhedral surfaces, shortest paths, geodesic distance, Delaunay triangulation}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.58
Segment Visibility Counting Queries in Polygons

Authors: Kevin Buchin, Bram Custers, Ivor van der Hoog, Maarten Löffler, Aleksandr Popov, Marcel Roeloffzen, and Frank Staals

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
Let P be a simple polygon with n vertices, and let A be a set of m points or line segments inside P. We develop data structures that can efficiently count the objects from A that are visible to a query point or a query segment. Our main aim is to obtain fast, O(polylog nm), query times, while using as little space as possible. In case the query is a single point, a simple visibility-polygon-based solution achieves O(log nm) query time using O(nm²) space. In case A also contains only points, we present a smaller, O(n + m^{2+ε} log n)-space, data structure based on a hierarchical decomposition of the polygon. Building on these results, we tackle the case where the query is a line segment and A contains only points. The main complication here is that the segment may intersect multiple regions of the polygon decomposition, and that a point may see multiple such pieces. Despite these issues, we show how to achieve O(log n log nm) query time using only O(nm^{2+ε} + n²) space. Finally, we show that we can even handle the case where the objects in A are segments with the same bounds.
Cite as

Kevin Buchin, Bram Custers, Ivor van der Hoog, Maarten Löffler, Aleksandr Popov, Marcel Roeloffzen, and Frank Staals. Segment Visibility Counting Queries in Polygons. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 58:1-58:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.ISAAC.2022.58,
  author =	{Buchin, Kevin and Custers, Bram and van der Hoog, Ivor and L\"{o}ffler, Maarten and Popov, Aleksandr and Roeloffzen, Marcel and Staals, Frank},
  title =	{{Segment Visibility Counting Queries in Polygons}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{58:1--58:16},
  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.58},
  URN =		{urn:nbn:de:0030-drops-173431},
  doi =		{10.4230/LIPIcs.ISAAC.2022.58},
  annote =	{Keywords: Visibility, Data Structure, Polygons, Complexity}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.29
Efficient Fréchet Distance Queries for Segments

Authors: Maike Buchin, Ivor van der Hoog, Tim Ophelders, Lena Schlipf, Rodrigo I. Silveira, and Frank Staals

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
We study the problem of constructing a data structure that can store a two-dimensional polygonal curve P, such that for any query segment ab one can efficiently compute the Fréchet distance between P and ab. First we present a data structure of size O(n log n) that can compute the Fréchet distance between P and a horizontal query segment ab in O(log n) time, where n is the number of vertices of P. In comparison to prior work, this significantly reduces the required space. We extend the type of queries allowed, as we allow a query to be a horizontal segment ab together with two points s, t ∈ P (not necessarily vertices), and ask for the Fréchet distance between ab and the curve of P in between s and t. Using O(nlog²n) storage, such queries take O(log³ n) time, simplifying and significantly improving previous results. We then generalize our results to query segments of arbitrary orientation. We present an O(nk^{3+ε}+n²) size data structure, where k ∈ [1,n] is a parameter the user can choose, and ε > 0 is an arbitrarily small constant, such that given any segment ab and two points s, t ∈ P we can compute the Fréchet distance between ab and the curve of P in between s and t in O((n/k)log²n+log⁴ n) time. This is the first result that allows efficient exact Fréchet distance queries for arbitrarily oriented segments. We also present two applications of our data structure. First, we show that our data structure allows us to compute a local δ-simplification (with respect to the Fréchet distance) of a polygonal curve in O(n^{5/2+ε}) time, improving a previous O(n³) time algorithm. Second, we show that we can efficiently find a translation of an arbitrary query segment ab that minimizes the Fréchet distance with respect to a subcurve of P.
Cite as

Maike Buchin, Ivor van der Hoog, Tim Ophelders, Lena Schlipf, Rodrigo I. Silveira, and Frank Staals. Efficient Fréchet Distance Queries for Segments. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 29:1-29:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.ESA.2022.29,
  author =	{Buchin, Maike and van der Hoog, Ivor and Ophelders, Tim and Schlipf, Lena and Silveira, Rodrigo I. and Staals, Frank},
  title =	{{Efficient Fr\'{e}chet Distance Queries for Segments}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{29:1--29:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva 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.2022.29},
  URN =		{urn:nbn:de:0030-drops-169671},
  doi =		{10.4230/LIPIcs.ESA.2022.29},
  annote =	{Keywords: Computational Geometry, Data Structures, Fr\'{e}chet distance}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.67
Chromatic k-Nearest Neighbor Queries

Authors: Thijs van der Horst, Maarten Löffler, and Frank Staals

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
Let P be a set of n colored points. We develop efficient data structures that store P and can answer chromatic k-nearest neighbor (k-NN) queries. Such a query consists of a query point q and a number k, and asks for the color that appears most frequently among the k points in P closest to q. Answering such queries efficiently is the key to obtain fast k-NN classifiers. Our main aim is to obtain query times that are independent of k while using near-linear space. We show that this is possible using a combination of two data structures. The first data structure allow us to compute a region containing exactly the k-nearest neighbors of a query point q, and the second data structure can then report the most frequent color in such a region. This leads to linear space data structures with query times of O(n^{1/2} log n) for points in ℝ¹, and with query times varying between O(n^{2/3}log^{2/3} n) and O(n^{5/6} polylog n), depending on the distance measure used, for points in ℝ². These results can be extended to work in higher dimensions as well. Since the query times are still fairly large we also consider approximations. If we are allowed to report a color that appears at least (1-ε)f^* times, where f^* is the frequency of the most frequent color, we obtain a query time of O(log n + log log_{1/(1-ε)} n) in ℝ¹ and expected query times ranging between Õ(n^{1/2}ε^{-3/2}) and Õ(n^{1/2}ε^{-5/2}) in ℝ² using near-linear space (ignoring polylogarithmic factors).
Cite as

Thijs van der Horst, Maarten Löffler, and Frank Staals. Chromatic k-Nearest Neighbor Queries. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 67:1-67:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{vanderhorst_et_al:LIPIcs.ESA.2022.67,
  author =	{van der Horst, Thijs and L\"{o}ffler, Maarten and Staals, Frank},
  title =	{{Chromatic k-Nearest Neighbor Queries}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{67:1--67:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva 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.2022.67},
  URN =		{urn:nbn:de:0030-drops-170055},
  doi =		{10.4230/LIPIcs.ESA.2022.67},
  annote =	{Keywords: data structure, nearest neighbor, classification}
}
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}
}
Document
DOI: 10.4230/LIPIcs.GIScience.2021.II.10
Terrain Prickliness: Theoretical Grounds for High Complexity Viewsheds

Authors: Ankush Acharyya, Ramesh K. Jallu, Maarten Löffler, Gert G.T. Meijer, Maria Saumell, Rodrigo I. Silveira, and Frank Staals

Published in: LIPIcs, Volume 208, 11th International Conference on Geographic Information Science (GIScience 2021) - Part II

Abstract
An important task in terrain analysis is computing viewsheds. A viewshed is the union of all the parts of the terrain that are visible from a given viewpoint or set of viewpoints. The complexity of a viewshed can vary significantly depending on the terrain topography and the viewpoint position. In this work we study a new topographic attribute, the prickliness, that measures the number of local maxima in a terrain from all possible angles of view. We show that the prickliness effectively captures the potential of terrains to have high complexity viewsheds. We present near-optimal algorithms to compute it for TIN terrains, and efficient approximate algorithms for raster DEMs. We validate the usefulness of the prickliness attribute with experiments in a large set of real terrains.
Cite as

Ankush Acharyya, Ramesh K. Jallu, Maarten Löffler, Gert G.T. Meijer, Maria Saumell, Rodrigo I. Silveira, and Frank Staals. Terrain Prickliness: Theoretical Grounds for High Complexity Viewsheds. In 11th International Conference on Geographic Information Science (GIScience 2021) - Part II. Leibniz International Proceedings in Informatics (LIPIcs), Volume 208, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{acharyya_et_al:LIPIcs.GIScience.2021.II.10,
  author =	{Acharyya, Ankush and Jallu, Ramesh K. and L\"{o}ffler, Maarten and Meijer, Gert G.T. and Saumell, Maria and Silveira, Rodrigo I. and Staals, Frank},
  title =	{{Terrain Prickliness: Theoretical Grounds for High Complexity Viewsheds}},
  booktitle =	{11th International Conference on Geographic Information Science (GIScience 2021) - Part II},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-208-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{208},
  editor =	{Janowicz, Krzysztof and Verstegen, Judith A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2021.II.10},
  URN =		{urn:nbn:de:0030-drops-147697},
  doi =		{10.4230/LIPIcs.GIScience.2021.II.10},
  annote =	{Keywords: Digital elevation model, Triangulated irregular network, Viewshed complexity}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.75
Kinetic Geodesic Voronoi Diagrams in a Simple Polygon

Authors: Matias Korman, André van Renssen, Marcel Roeloffzen, and Frank Staals

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

Abstract
We study the geodesic Voronoi diagram of a set S of n linearly moving sites inside a static simple polygon P with m vertices. We identify all events where the structure of the Voronoi diagram changes, bound the number of such events, and then develop a kinetic data structure (KDS) that maintains the geodesic Voronoi diagram as the sites move. To this end, we first analyze how often a single bisector, defined by two sites, or a single Voronoi center, defined by three sites, can change. For both these structures we prove that the number of such changes is at most O(m³), and that this is tight in the worst case. Moreover, we develop compact, responsive, local, and efficient kinetic data structures for both structures. Our data structures use linear space and process a worst-case optimal number of events. Our bisector KDS handles each event in O(log m) time, and our Voronoi center handles each event in O(log² m) time. Both structures can be extended to efficiently support updating the movement of the sites as well. Using these data structures as building blocks we obtain a compact KDS for maintaining the full geodesic Voronoi diagram.
Cite as

Matias Korman, André van Renssen, Marcel Roeloffzen, and Frank Staals. Kinetic Geodesic Voronoi Diagrams in a Simple Polygon. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 75:1-75:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{korman_et_al:LIPIcs.ICALP.2020.75,
  author =	{Korman, Matias and van Renssen, Andr\'{e} and Roeloffzen, Marcel and Staals, Frank},
  title =	{{Kinetic Geodesic Voronoi Diagrams in a Simple Polygon}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{75:1--75:17},
  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.75},
  URN =		{urn:nbn:de:0030-drops-124820},
  doi =		{10.4230/LIPIcs.ICALP.2020.75},
  annote =	{Keywords: kinetic data structure, simple polygon, geodesic voronoi diagram}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2020.23
Trajectory Visibility

Authors: Patrick Eades, Ivor van der Hoog, Maarten Löffler, and Frank Staals

Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)

Abstract
We study the problem of testing whether there exists a time at which two entities moving along different piece-wise linear trajectories among polygonal obstacles are mutually visible. We study several variants, depending on whether or not the obstacles form a simple polygon, trajectories may intersect the polygon edges, and both or only one of the entities are moving. For constant complexity trajectories contained in a simple polygon with n vertices, we provide an 𝒪(n) time algorithm to test if there is a time at which the entities can see each other. If the polygon contains holes, we present an 𝒪(n log n) algorithm. We show that this is tight. We then consider storing the obstacles in a data structure, such that queries consisting of two line segments can be efficiently answered. We show that for all variants it is possible to answer queries in sublinear time using polynomial space and preprocessing time. As a critical intermediate step, we provide an efficient solution to a problem of independent interest: preprocess a convex polygon such that we can efficiently test intersection with a quadratic curve segment. If the obstacles form a simple polygon, this allows us to answer visibility queries in 𝒪(n³/4log³ n) time using 𝒪(nlog⁵ n) space. For more general obstacles the query time is 𝒪(log^k n), for a constant but large value k, using 𝒪(n^{3k}) space. We provide more efficient solutions when one of the entities remains stationary.
Cite as

Patrick Eades, Ivor van der Hoog, Maarten Löffler, and Frank Staals. Trajectory Visibility. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 23:1-23:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{eades_et_al:LIPIcs.SWAT.2020.23,
  author =	{Eades, Patrick and van der Hoog, Ivor and L\"{o}ffler, Maarten and Staals, Frank},
  title =	{{Trajectory Visibility}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{23:1--23:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  editor =	{Albers, Susanne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.23},
  URN =		{urn:nbn:de:0030-drops-122701},
  doi =		{10.4230/LIPIcs.SWAT.2020.23},
  annote =	{Keywords: trajectories, visibility, data structures, semi-algebraic range searching}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.52
Convex Partial Transversals of Planar Regions

Authors: Vahideh Keikha, Mees van de Kerkhof, Marc van Kreveld, Irina Kostitsyna, Maarten Löffler, Frank Staals, Jérôme Urhausen, Jordi L. Vermeulen, and Lionov Wiratma

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
We consider the problem of testing, for a given set of planar regions R and an integer k, whether there exists a convex shape whose boundary intersects at least k regions of R. We provide polynomial-time algorithms for the case where the regions are disjoint axis-aligned rectangles or disjoint line segments with a constant number of orientations. On the other hand, we show that the problem is NP-hard when the regions are intersecting axis-aligned rectangles or 3-oriented line segments. For several natural intermediate classes of shapes (arbitrary disjoint segments, intersecting 2-oriented segments) the problem remains open.
Cite as

Vahideh Keikha, Mees van de Kerkhof, Marc van Kreveld, Irina Kostitsyna, Maarten Löffler, Frank Staals, Jérôme Urhausen, Jordi L. Vermeulen, and Lionov Wiratma. Convex Partial Transversals of Planar Regions. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 52:1-52:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{keikha_et_al:LIPIcs.ISAAC.2018.52,
  author =	{Keikha, Vahideh and van de Kerkhof, Mees and van Kreveld, Marc and Kostitsyna, Irina and L\"{o}ffler, Maarten and Staals, Frank and Urhausen, J\'{e}r\^{o}me and Vermeulen, Jordi L. and Wiratma, Lionov},
  title =	{{Convex Partial Transversals of Planar Regions}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{52:1--52:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.52},
  URN =		{urn:nbn:de:0030-drops-100003},
  doi =		{10.4230/LIPIcs.ISAAC.2018.52},
  annote =	{Keywords: computational geometry, algorithms, NP-hardness, convex transversals}
}
Document
Short Paper
DOI: 10.4230/LIPIcs.GISCIENCE.2018.64
An Experimental Comparison of Two Definitions for Groups of Moving Entities (Short Paper)

Authors: Lionov Wiratma, Maarten Löffler, and Frank Staals

Published in: LIPIcs, Volume 114, 10th International Conference on Geographic Information Science (GIScience 2018)

Abstract
Two of the grouping definitions for trajectories that have been developed in recent years allow a continuous motion model and allow varying shape groups. One of these definitions was suggested as a refinement of the other. In this paper we perform an experimental comparison to highlight the differences in these two definitions on various data sets.
Cite as

Lionov Wiratma, Maarten Löffler, and Frank Staals. An Experimental Comparison of Two Definitions for Groups of Moving Entities (Short Paper). In 10th International Conference on Geographic Information Science (GIScience 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 114, pp. 64:1-64:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{wiratma_et_al:LIPIcs.GISCIENCE.2018.64,
  author =	{Wiratma, Lionov and L\"{o}ffler, Maarten and Staals, Frank},
  title =	{{An Experimental Comparison of Two Definitions for Groups of Moving Entities}},
  booktitle =	{10th International Conference on Geographic Information Science (GIScience 2018)},
  pages =	{64:1--64:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-083-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{114},
  editor =	{Winter, Stephan and Griffin, Amy and Sester, Monika},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GISCIENCE.2018.64},
  URN =		{urn:nbn:de:0030-drops-93928},
  doi =		{10.4230/LIPIcs.GISCIENCE.2018.64},
  annote =	{Keywords: Trajectories, grouping algorithms, experimental comparison}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.4
Improved Dynamic Geodesic Nearest Neighbor Searching in a Simple Polygon

Authors: Pankaj K. Agarwal, Lars Arge, and Frank Staals

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
We present an efficient dynamic data structure that supports geodesic nearest neighbor queries for a set S of point sites in a static simple polygon P. Our data structure allows us to insert a new site in S, delete a site from S, and ask for the site in S closest to an arbitrary query point q in P. All distances are measured using the geodesic distance, that is, the length of the shortest path that is completely contained in P. Our data structure achieves polylogarithmic update and query times, and uses O(n log^3n log m + m) space, where n is the number of sites in S and m is the number of vertices in P. The crucial ingredient in our data structure is an implicit representation of a vertical shallow cutting of the geodesic distance functions. We show that such an implicit representation exists, and that we can compute it efficiently.
Cite as

Pankaj K. Agarwal, Lars Arge, and Frank Staals. Improved Dynamic Geodesic Nearest Neighbor Searching in a Simple Polygon. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 4:1-4:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.SoCG.2018.4,
  author =	{Agarwal, Pankaj K. and Arge, Lars and Staals, Frank},
  title =	{{Improved Dynamic Geodesic Nearest Neighbor Searching in a Simple Polygon}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{4:1--4:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.4},
  URN =		{urn:nbn:de:0030-drops-87175},
  doi =		{10.4230/LIPIcs.SoCG.2018.4},
  annote =	{Keywords: data structure, simple polygon, geodesic distance, nearest neighbor searching, shallow cutting}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2016.48
A Refined Definition for Groups of Moving Entities and its Computation

Authors: Marc van Kreveld, Maarten Löffler, Frank Staals, and Lionov Wiratma

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract
One of the important tasks in the analysis of spatio-temporal data collected from moving entities is to find a group: a set of entities that travel together for a sufficiently long period of time. Buchin et al. [JoCG, 2015] introduce a formal definition of groups, analyze its mathematical structure, and present efficient algorithms for computing all maximal groups in a given set of trajectories. In this paper, we refine their definition and argue that our proposed definition corresponds better to human intuition in certain cases, particularly in dense environments. We present algorithms to compute all maximal groups from a set of moving entities according to the new definition. For a set of n moving entities in R^1, specified by linear interpolation in a sequence of tau time stamps, we show that all maximal groups can be computed in O(tau^2 n^4) time. A similar approach applies if the time stamps of entities are not the same, at the cost of a small extra factor of alpha(n) in the running time. In higher dimensions, we can compute all maximal groups in O(tau^2 n^5 log n) time (for any constant number of dimensions). We also show that one tau factor can be traded for a much higher dependence on n by giving a O(tau n^4 2^n) algorithm for the same problem. Consequently, we give a linear-time algorithm when the number of entities is constant and the input size relates to the number of time stamps of each entity. Finally, we provide a construction to show that it might be difficult to develop an algorithm with polynomial dependence on n and linear dependence on tau.
Cite as

Marc van Kreveld, Maarten Löffler, Frank Staals, and Lionov Wiratma. A Refined Definition for Groups of Moving Entities and its Computation. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 48:1-48:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{vankreveld_et_al:LIPIcs.ISAAC.2016.48,
  author =	{van Kreveld, Marc and L\"{o}ffler, Maarten and Staals, Frank and Wiratma, Lionov},
  title =	{{A Refined Definition for Groups of Moving Entities and its Computation}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{48:1--48:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.48},
  URN =		{urn:nbn:de:0030-drops-68188},
  doi =		{10.4230/LIPIcs.ISAAC.2016.48},
  annote =	{Keywords: moving entities, trajectories, grouping, computational geometry}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.27
Homotopy Measures for Representative Trajectories

Authors: Erin Chambers, Irina Kostitsyna, Maarten Löffler, and Frank Staals

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
An important task in trajectory analysis is defining a meaningful representative for a cluster of similar trajectories. Formally defining and computing such a representative r is a challenging problem. We propose and discuss two new definitions, both of which use only the geometry of the input trajectories. The definitions are based on the homotopy area as a measure of similarity between two curves, which is a minimum area swept by all possible deformations of one curve into the other. In the first definition we wish to minimize the maximum homotopy area between r and any input trajectory, whereas in the second definition we wish to minimize the sum of the homotopy areas between r and the input trajectories. For both definitions computing an optimal representative is NP-hard. However, for the case of minimizing the sum of the homotopy areas, an optimal representative can be found efficiently in a natural class of restricted inputs, namely, when the arrangement of trajectories forms a directed acyclic graph.
Cite as

Erin Chambers, Irina Kostitsyna, Maarten Löffler, and Frank Staals. Homotopy Measures for Representative Trajectories. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 27:1-27:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{chambers_et_al:LIPIcs.ESA.2016.27,
  author =	{Chambers, Erin and Kostitsyna, Irina and L\"{o}ffler, Maarten and Staals, Frank},
  title =	{{Homotopy Measures for Representative Trajectories}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{27:1--27:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.27},
  URN =		{urn:nbn:de:0030-drops-63783},
  doi =		{10.4230/LIPIcs.ESA.2016.27},
  annote =	{Keywords: trajectory analysis, representative trajectory, homotopy area}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.49
On the Complexity of Minimum-Link Path Problems

Authors: Irina Kostitsyna, Maarten Löffler, Valentin Polishchuk, and Frank Staals

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
We revisit the minimum-link path problem: Given a polyhedral domain and two points in it, connect the points by a polygonal path with minimum number of edges. We consider settings where the min-link path's vertices or edges can be restricted to lie on the boundary of the domain, or can be in its interior. Our results include bit complexity bounds, a novel general hardness construction, and a polynomial-time approximation scheme. We fully characterize the situation in 2D, and provide first results in dimensions 3 and higher for several versions of the problem. Concretely, our results resolve several open problems. We prove that computing the minimum-link diffuse reflection path, motivated by ray tracing in computer graphics, is NP-hard, even for two-dimensional polygonal domains with holes. This has remained an open problem [Ghosh et al. 2012] despite a large body of work on the topic. We also resolve the open problem from [Mitchell et al. 1992] mentioned in the handbook [Goodman and O'Rourke, 2004] (see Chapter 27.5, Open problem 3) and The Open Problems Project [Demaine et al. TOPP] (see Problem 22): "What is the complexity of the minimum-link path problem in 3-space?" Our results imply that the problem is NP-hard even on terrains (and hence, due to discreteness of the answer, there is no FPTAS unless P=NP), but admits a PTAS.
Cite as

Irina Kostitsyna, Maarten Löffler, Valentin Polishchuk, and Frank Staals. On the Complexity of Minimum-Link Path Problems. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 49:1-49:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kostitsyna_et_al:LIPIcs.SoCG.2016.49,
  author =	{Kostitsyna, Irina and L\"{o}ffler, Maarten and Polishchuk, Valentin and Staals, Frank},
  title =	{{On the Complexity of Minimum-Link Path Problems}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{49:1--49:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.49},
  URN =		{urn:nbn:de:0030-drops-59412},
  doi =		{10.4230/LIPIcs.SoCG.2016.49},
  annote =	{Keywords: minimum-linkpath, diffuse reflection, terrain, bit complexity, NP-hardness}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.61
Grouping Time-Varying Data for Interactive Exploration

Authors: Arthur van Goethem, Marc van Kreveld, Maarten Löffler, Bettina Speckmann, and Frank Staals

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
We present algorithms and data structures that support the interactive analysis of the grouping structure of one-, two-, or higher-dimensional time-varying data while varying all defining parameters. Grouping structures characterise important patterns in the temporal evaluation of sets of time-varying data. We follow Buchin et al. [JoCG 2015] who define groups using three parameters: group-size, group-duration, and inter-entity distance. We give upper and lower bounds on the number of maximal groups over all parameter values, and show how to compute them efficiently. Furthermore, we describe data structures that can report changes in the set of maximal groups in an output-sensitive manner. Our results hold in R^d for fixed d.
Cite as

Arthur van Goethem, Marc van Kreveld, Maarten Löffler, Bettina Speckmann, and Frank Staals. Grouping Time-Varying Data for Interactive Exploration. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 61:1-61:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{vangoethem_et_al:LIPIcs.SoCG.2016.61,
  author =	{van Goethem, Arthur and van Kreveld, Marc and L\"{o}ffler, Maarten and Speckmann, Bettina and Staals, Frank},
  title =	{{Grouping Time-Varying Data for Interactive Exploration}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{61:1--61:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.61},
  URN =		{urn:nbn:de:0030-drops-59539},
  doi =		{10.4230/LIPIcs.SoCG.2016.61},
  annote =	{Keywords: Trajectory, Time series, Moving entity, Grouping, Algorithm, Data structure}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.674
Trajectory Grouping Structure under Geodesic Distance

Authors: Irina Kostitsyna, Marc van Kreveld, Maarten Löffler, Bettina Speckmann, and Frank Staals

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract
In recent years trajectory data has become one of the main types of geographic data, and hence algorithmic tools to handle large quantities of trajectories are essential. A single trajectory is typically represented as a sequence of time-stamped points in the plane. In a collection of trajectories one wants to detect maximal groups of moving entities and their behaviour (merges and splits) over time. This information can be summarized in the trajectory grouping structure. Significantly extending the work of Buchin et al. [WADS 2013] into a realistic setting, we show that the trajectory grouping structure can be computed efficiently also if obstacles are present and the distance between the entities is measured by geodesic distance. We bound the number of critical events: times at which the distance between two subsets of moving entities is exactly epsilon, where epsilon is the threshold distance that determines whether two entities are close enough to be in one group. In case the n entities move in a simple polygon along trajectories with tau vertices each we give an O(tau n^2) upper bound, which is tight in the worst case. In case of well-spaced obstacles we give an O(tau(n^2 + m lambda_4(n))) upper bound, where m is the total complexity of the obstacles, and lambda_s(n) denotes the maximum length of a Davenport-Schinzel sequence of n symbols of order s. In case of general obstacles we give an O(tau min(n^2 + m^3 lambda_4(n), n^2m^2)) upper bound. Furthermore, for all cases we provide efficient algorithms to compute the critical events, which in turn leads to efficient algorithms to compute the trajectory grouping structure.
Cite as

Irina Kostitsyna, Marc van Kreveld, Maarten Löffler, Bettina Speckmann, and Frank Staals. Trajectory Grouping Structure under Geodesic Distance. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 674-688, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{kostitsyna_et_al:LIPIcs.SOCG.2015.674,
  author =	{Kostitsyna, Irina and van Kreveld, Marc and L\"{o}ffler, Maarten and Speckmann, Bettina and Staals, Frank},
  title =	{{Trajectory Grouping Structure under Geodesic Distance}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{674--688},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.674},
  URN =		{urn:nbn:de:0030-drops-51212},
  doi =		{10.4230/LIPIcs.SOCG.2015.674},
  annote =	{Keywords: moving entities, trajectories, grouping, computational geometry}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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