10 Search Results for "Vahrenhold, Jan"

Document
DOI: 10.4230/LIPIcs.ESA.2025.84
Property Testing of Curve Similarity

Authors: Peyman Afshani, Maike Buchin, Anne Driemel, Marena Richter, and Sampson Wong

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

Abstract
We propose sublinear algorithms for probabilistic testing of the discrete and continuous Fréchet distance - a standard similarity measure for curves. We assume the algorithm is given access to the input curves via a query oracle: a query returns the set of vertices of the curve that lie within a radius δ of a specified vertex of the other curve. The goal is to use a small number of queries to determine with constant probability whether the two curves are similar (i.e., their discrete Fréchet distance is at most δ) or they are "ε-far" (for 0 < ε < 2) from being similar, i.e., more than an ε-fraction of the two curves must be ignored for them to become similar. We present two algorithms which are sublinear assuming that the curves are t-approximate shortest paths in the ambient metric space, for some t ≪ n. The first algorithm uses O(t/ε log t/ε) queries and is given the value of t in advance. The second algorithm does not have explicit knowledge of the value of t and therefore needs to gain implicit knowledge of the straightness of the input curves through its queries. We show that the discrete Fréchet distance can still be tested using roughly O({t³+t² log n}/ε) queries ignoring logarithmic factors in t. Our algorithms work in a matrix representation of the input and may be of independent interest to matrix testing. Our algorithms use a mild uniform sampling condition that constrains the edge lengths of the curves, similar to a polynomially bounded aspect ratio. Applied to testing the continuous Fréchet distance of t-straight curves, our algorithms can be used for (1+ε')-approximate testing using essentially the same bounds as stated above with an additional factor of poly(1/(ε')).
Cite as

Peyman Afshani, Maike Buchin, Anne Driemel, Marena Richter, and Sampson Wong. Property Testing of Curve Similarity. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 84:1-84:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{afshani_et_al:LIPIcs.ESA.2025.84,
  author =	{Afshani, Peyman and Buchin, Maike and Driemel, Anne and Richter, Marena and Wong, Sampson},
  title =	{{Property Testing of Curve Similarity}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{84:1--84:16},
  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.84},
  URN =		{urn:nbn:de:0030-drops-245522},
  doi =		{10.4230/LIPIcs.ESA.2025.84},
  annote =	{Keywords: Fr\'{e}chet distance, Trajectory Analysis, Curve Similarity, Property Testing, Monotonicity Testing}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.36
Faster Fréchet Distance Under Transformations

Authors: Kevin Buchin, Maike Buchin, Zijin Huang, André Nusser, and Sampson Wong

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We study the problem of computing the Fréchet distance between two polygonal curves under transformations. First, we consider translations in the Euclidean plane. Given two curves π and σ of total complexity n and a threshold δ ≥ 0, we present an 𝒪̃(n^{7 + 1/3}) time algorithm to determine whether there exists a translation t ∈ ℝ² such that the Fréchet distance between π and σ + t is at most δ. This improves on the previous best result, which is an 𝒪(n⁸) time algorithm. We then generalize this result to any class of rationally parameterized transformations, which includes translation, rotation, scaling, and arbitrary affine transformations. For a class T of rationally parametrized transformations with k degrees of freedom, we show that one can determine whether there is a transformation τ ∈ T such that the Fréchet distance between π and τ(σ) is at most δ in 𝒪̃(n^{3k+4/3}) time.
Cite as

Kevin Buchin, Maike Buchin, Zijin Huang, André Nusser, and Sampson Wong. Faster Fréchet Distance Under Transformations. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 36:1-36:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.ICALP.2025.36,
  author =	{Buchin, Kevin and Buchin, Maike and Huang, Zijin and Nusser, Andr\'{e} and Wong, Sampson},
  title =	{{Faster Fr\'{e}chet Distance Under Transformations}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{36:1--36:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.36},
  URN =		{urn:nbn:de:0030-drops-234137},
  doi =		{10.4230/LIPIcs.ICALP.2025.36},
  annote =	{Keywords: Fr\'{e}chet distance, curve similarity, shape matching}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.78
Efficient Greedy Discrete Subtrajectory Clustering

Authors: Ivor van der Hoog, Lara Ost, Eva Rotenberg, and Daniel Rutschmann

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

Abstract
We cluster a set of trajectories 𝒯 using subtrajectories of 𝒯. We require for a clustering C that any two subtrajectories (𝒯[a, b], 𝒯[c, d]) in a cluster have disjoint intervals [a,b] and [c, d]. Clustering quality may be measured by the number of clusters, the number of vertices of 𝒯 that are absent from the clustering, and by the Fréchet distance between subtrajectories in a cluster. A Δ-cluster of 𝒯 is a cluster 𝒫 of subtrajectories of 𝒯 with a centre P ∈ 𝒫, where all subtrajectories in 𝒫 have Fréchet distance at most Δ to P. Buchin, Buchin, Gudmundsson, Löffler and Luo present two O(n² + n m 𝓁)-time algorithms: SC(max, 𝓁, Δ, 𝒯) computes a single Δ-cluster where P has at least 𝓁 vertices and maximises the cardinality m of 𝒫. SC(m, max, Δ, 𝒯) computes a single Δ-cluster where 𝒫 has cardinality m and maximises the complexity 𝓁 of P. In this paper, which is a mixture of algorithms engineering and theoretical insights, we use such maximum-cardinality clusters in a greedy clustering algorithm. We first provide an efficient implementation of SC(max, 𝓁, Δ, 𝒯) and SC(m, max, Δ, 𝒯) that significantly outperforms previous implementations. Next, we use these functions as a subroutine in a greedy clustering algorithm, which performs well when compared to existing subtrajectory clustering algorithms on real-world data. Finally, we observe that, for fixed Δ and 𝒯, these two functions always output a point on the Pareto front of some bivariate function θ(𝓁, m). We design a new algorithm PSC(Δ, 𝒯) that in O(n² log⁴ n) time computes a 2-approximation of this Pareto front. This yields a broader set of candidate clusters, with comparable quality to the output of the previous functions. We show that using PSC(Δ, 𝒯) as a subroutine improves the clustering quality and performance even further.
Cite as

Ivor van der Hoog, Lara Ost, Eva Rotenberg, and Daniel Rutschmann. Efficient Greedy Discrete Subtrajectory Clustering. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 78:1-78:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{vanderhoog_et_al:LIPIcs.SoCG.2025.78,
  author =	{van der Hoog, Ivor and Ost, Lara and Rotenberg, Eva and Rutschmann, Daniel},
  title =	{{Efficient Greedy Discrete Subtrajectory Clustering}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{78:1--78:20},
  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.78},
  URN =		{urn:nbn:de:0030-drops-232308},
  doi =		{10.4230/LIPIcs.SoCG.2025.78},
  annote =	{Keywords: Algorithms engineering, Fr\'{e}chet distance, subtrajectory clustering}
}
Document
DOI: 10.4230/DagRep.14.6.108
Teaching Support Systems for Formal Foundations of Computer Science (Dagstuhl Seminar 24251)

Authors: Tiffany Barnes, Jan Vahrenhold, Thomas Zeume, and Florian Schmalstieg

Published in: Dagstuhl Reports, Volume 14, Issue 6 (2024)

Abstract
Introductory courses on formal foundations of computer science - including basic courses on theoretical computer science (regular and context-free languages, computability theory, and complexity theory) as well as on logic in computer science (propositional and first-order logic, modeling, and algorithms for evaluation and satisfaction of formulas) - are a cornerstone of computer science curricula, yet many students struggle with their often theoretical contents. The recent influx of students in computer science, as well as the shift towards the inclusion of more online-based teaching ask for advanced teaching support systems that aid both students and instructors. This Dagstuhl Seminar focussed on fostering discussion between researchers in computing education, builders of systems for teaching formal foundations, as well as instructors of these foundations in order to facilitate more robust research and development of systems to support teaching and learning of the formal foundations of computer science.
Cite as

Tiffany Barnes, Jan Vahrenhold, Thomas Zeume, and Florian Schmalstieg. Teaching Support Systems for Formal Foundations of Computer Science (Dagstuhl Seminar 24251). In Dagstuhl Reports, Volume 14, Issue 6, pp. 108-129, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Article{barnes_et_al:DagRep.14.6.108,
  author =	{Barnes, Tiffany and Vahrenhold, Jan and Zeume, Thomas and Schmalstieg, Florian},
  title =	{{Teaching Support Systems for Formal Foundations of Computer Science (Dagstuhl Seminar 24251)}},
  pages =	{108--129},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2024},
  volume =	{14},
  number =	{6},
  editor =	{Barnes, Tiffany and Vahrenhold, Jan and Zeume, Thomas and Schmalstieg, Florian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.14.6.108},
  URN =		{urn:nbn:de:0030-drops-227301},
  doi =		{10.4230/DagRep.14.6.108},
  annote =	{Keywords: artificial intelligence in education, computing education research, educational data mining, formal foundations of computer science, intelligent tutoring systems, user modeling and adaptive personalization, user studies}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2024.55
Optimal Offline ORAM with Perfect Security via Simple Oblivious Priority Queues

Authors: Thore Thießen and Jan Vahrenhold

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

Abstract
Oblivious RAM (ORAM) is a well-researched primitive to hide the memory access pattern of a RAM computation; it has a variety of applications in trusted computing, outsourced storage, and multiparty computation. In this paper, we study the so-called offline ORAM in which the sequence of memory access locations to be hidden is known in advance. Apart from their theoretical significance, offline ORAMs can be used to construct efficient oblivious algorithms. We obtain the first optimal offline ORAM with perfect security from oblivious priority queues via time-forward processing. For this, we present a simple construction of an oblivious priority queue with perfect security. Our construction achieves an asymptotically optimal (amortized) runtime of Θ(log N) per operation for a capacity of N elements and is of independent interest. Building on our construction, we additionally present efficient external-memory instantiations of our oblivious, perfectly-secure construction: For the cache-aware setting, we match the optimal I/O complexity of Θ(1/B log N/M) per operation (amortized), and for the cache-oblivious setting we achieve a near-optimal I/O complexity of O(1/B log N/M log log_M N) per operation (amortized).
Cite as

Thore Thießen and Jan Vahrenhold. Optimal Offline ORAM with Perfect Security via Simple Oblivious Priority Queues. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 55:1-55:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{thieen_et_al:LIPIcs.ISAAC.2024.55,
  author =	{Thie{\ss}en, Thore and Vahrenhold, Jan},
  title =	{{Optimal Offline ORAM with Perfect Security via Simple Oblivious Priority Queues}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{55:1--55:18},
  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.55},
  URN =		{urn:nbn:de:0030-drops-221832},
  doi =		{10.4230/LIPIcs.ISAAC.2024.55},
  annote =	{Keywords: offline ORAM, oblivious priority queue, perfect security, external memory algorithm, cache-oblivious algorithm}
}
Document
DOI: 10.4230/DagRep.9.7.1
Notional Machines and Programming Language Semantics in Education (Dagstuhl Seminar 19281)

Authors: Mark Guzdial, Shriram Krishnamurthi, Juha Sorva, and Jan Vahrenhold

Published in: Dagstuhl Reports, Volume 9, Issue 7 (2020)

Abstract
A formal semantics of a language serves many purposes. It can help debug the language's design, be used to prove type soundness, and guide optimizers to confirm that their work is correctness-preserving. Formal semantics are evaluated by several criteria: full abstraction, adequacy, soundness and completeness, faithfulness to an underlying implementation, and so on. Unfortunately, we know relatively little about how non-experts, such as students, actually employ a semantics. Which models are they able to grasp? How useful are these as they explain or debug programs? How does their use of models evolve with the kinds of programs they write? And does studying these kinds of questions yield any new insights into forms of semantics? This Dagstuhl Seminar intended to bridge this gap. It brought together representatives of the two communities-who usually travel in non-intersecting circles-to enable mutual understanding and cross-pollination. The Programming Languages community uses mathematics and focuses on formal results; the Computing Education Research community uses social science methods and focuses on the impact on humans. Neither is superior: both are needed to arrive at a comprehensive solution to creating tools for learning.
Cite as

Mark Guzdial, Shriram Krishnamurthi, Juha Sorva, and Jan Vahrenhold. Notional Machines and Programming Language Semantics in Education (Dagstuhl Seminar 19281). In Dagstuhl Reports, Volume 9, Issue 7, pp. 1-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{guzdial_et_al:DagRep.9.7.1,
  author =	{Guzdial, Mark and Krishnamurthi, Shriram and Sorva, Juha and Vahrenhold, Jan},
  title =	{{Notional Machines and Programming Language Semantics in Education (Dagstuhl Seminar 19281)}},
  pages =	{1--23},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{9},
  number =	{7},
  editor =	{Guzdial, Mark and Krishnamurthi, Shriram and Sorva, Juha and Vahrenhold, Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.9.7.1},
  URN =		{urn:nbn:de:0030-drops-116272},
  doi =		{10.4230/DagRep.9.7.1},
  annote =	{Keywords: computing education research, formal semantics, misconceptions, notional machines}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2016.60
Approximate Shortest Distances Among Smooth Obstacles in 3D

Authors: Christian Scheffer and Jan Vahrenhold

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

Abstract
We consider the classic all-pairs-shortest-paths (APSP) problem in a three-dimensional environment where paths have to avoid a set of smooth obstacles whose surfaces are represented by discrete point sets with n sample points in total. We show that if the point sets represent epsilon-samples of the underlying surfaces, (1 ± O(sqrt{epsilon}))-approximations of the distances between all pairs of sample points can be computed in O(n^{5/2} log^2 n) time.
Cite as

Christian Scheffer and Jan Vahrenhold. Approximate Shortest Distances Among Smooth Obstacles in 3D. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 60:1-60:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{scheffer_et_al:LIPIcs.ISAAC.2016.60,
  author =	{Scheffer, Christian and Vahrenhold, Jan},
  title =	{{Approximate Shortest Distances Among Smooth Obstacles in 3D}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{60:1--60:13},
  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.60},
  URN =		{urn:nbn:de:0030-drops-68292},
  doi =		{10.4230/LIPIcs.ISAAC.2016.60},
  annote =	{Keywords: Geodesic distances; approximation algorithm; epsilon sample}
}
Document
DOI: 10.4230/DagRep.6.2.78
Assessing Learning In Introductory Computer Science (Dagstuhl Seminar 16072)

Authors: Michael E. Caspersen, Kathi Fisler, and Jan Vahrenhold

Published in: Dagstuhl Reports, Volume 6, Issue 2 (2016)

Abstract
This seminar discussed educational outcomes for first-year (university-level) computer science. We explored which outcomes were widely shared across both countries and individual universities, best practices for assessing outcomes, and research projects that would significantly advance assessment of learning in computer science. We considered both technical and professional outcomes (some narrow and some broad) as well as how to create assessments that focused on individual learners. Several concrete research projects took shape during the seminar and are being pursued by some participants.
Cite as

Michael E. Caspersen, Kathi Fisler, and Jan Vahrenhold. Assessing Learning In Introductory Computer Science (Dagstuhl Seminar 16072). In Dagstuhl Reports, Volume 6, Issue 2, pp. 78-96, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Article{caspersen_et_al:DagRep.6.2.78,
  author =	{Caspersen, Michael E. and Fisler, Kathi and Vahrenhold, Jan},
  title =	{{Assessing Learning In Introductory Computer Science (Dagstuhl Seminar 16072)}},
  pages =	{78--96},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{6},
  number =	{2},
  editor =	{Caspersen, Michael E. and Fisler, Kathi and Vahrenhold, Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.6.2.78},
  URN =		{urn:nbn:de:0030-drops-58899},
  doi =		{10.4230/DagRep.6.2.78},
  annote =	{Keywords: Assessment, Learning Objectives}
}
Document
DOI: 10.4230/DagSemProc.06091.4
In-Place Randomized Slope-Selection

Authors: Henrik Blunck and Jan Vahrenhold

Published in: Dagstuhl Seminar Proceedings, Volume 6091, Data Structures (2006)

Abstract
Slope selection is a well-known algorithmic tool used in the context of computing robust estimators for fitting a line to a collection $mathcal{P}$ of $n$ points in the plane. We demonstrate that it is possible to perform slope selection in expected $mathcal{O}(n log n)$ time using only constant extra space in addition to the space needed for representing the input. Our solution is based upon a space-efficient variant of Matouv{s}ek's randomized interpolation search, and we believe that the techniques developed in this paper will prove helpful in the design of space-efficient randomized algorithms using samples. To underline this, we also sketch how to compute the repeated median line estimator in an in-place setting.
Cite as

Henrik Blunck and Jan Vahrenhold. In-Place Randomized Slope-Selection. In Data Structures. Dagstuhl Seminar Proceedings, Volume 6091, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{blunck_et_al:DagSemProc.06091.4,
  author =	{Blunck, Henrik and Vahrenhold, Jan},
  title =	{{In-Place Randomized Slope-Selection}},
  booktitle =	{Data Structures},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6091},
  editor =	{Lars Arge and Robert Sedgewick and Dorothea Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06091.4},
  URN =		{urn:nbn:de:0030-drops-8390},
  doi =		{10.4230/DagSemProc.06091.4},
  annote =	{Keywords: In-Place Algorithms, Slope Selection}
}
Document
DOI: 10.4230/DagSemProc.04301.2
A Simple Algorithm for I/O-efficiently Pruning Dense Spanners

Authors: Joachim Gudmundsson and Jan Vahrenhold

Published in: Dagstuhl Seminar Proceedings, Volume 4301, Cache-Oblivious and Cache-Aware Algorithms (2005)

Abstract
Given a geometric graph $G=(S,E)$ in $R^d$ with constant dilation $t$, and a positive constant $\epsilon$, we show how to construct a $(1+\epsilon)$-spanner of $G$ with $O(|S|)$ edges using $O(sort(|E|))$ I/O operations.
Cite as

Joachim Gudmundsson and Jan Vahrenhold. A Simple Algorithm for I/O-efficiently Pruning Dense Spanners. In Cache-Oblivious and Cache-Aware Algorithms. Dagstuhl Seminar Proceedings, Volume 4301, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{gudmundsson_et_al:DagSemProc.04301.2,
  author =	{Gudmundsson, Joachim and Vahrenhold, Jan},
  title =	{{A Simple Algorithm for I/O-efficiently Pruning Dense Spanners}},
  booktitle =	{Cache-Oblivious and Cache-Aware Algorithms},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4301},
  editor =	{Lars Arge and Michael A. Bender and Erik Demaine and Charles Leiserson and Kurt Mehlhorn},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04301.2},
  URN =		{urn:nbn:de:0030-drops-1566},
  doi =		{10.4230/DagSemProc.04301.2},
  annote =	{Keywords: No keywords}
}
  • Refine by Type
  • 10 Document/PDF
  • 4 Document/HTML

  • Refine by Publication Year
  • 3 2025
  • 2 2024
  • 1 2019
  • 2 2016
  • 1 2006
  • Show More...

  • Refine by Author
  • 7 Vahrenhold, Jan
  • 2 Buchin, Maike
  • 2 Wong, Sampson
  • 1 Afshani, Peyman
  • 1 Barnes, Tiffany
  • Show More...

  • Refine by Series/Journal
  • 5 LIPIcs
  • 3 DagRep
  • 2 DagSemProc

  • Refine by Classification
  • 2 Theory of computation → Computational geometry
  • 1 Applied computing → Education
  • 1 Social and professional topics → Computing education
  • 1 Theory of computation
  • 1 Theory of computation → Cryptographic protocols
  • Show More...

  • Refine by Keyword
  • 3 Fréchet distance
  • 2 computing education research
  • 1 Algorithms engineering
  • 1 Assessment
  • 1 Curve Similarity
  • Show More...

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