9 citations · 19 across the 18 of their papers we have counts for
29 papers · 1 filter
A Strongly-Subquadratic -Approximation for the Fréchet Distance for Paths in Metric Spaces
Thijs van der Horst, Tim Ophelders
The Fréchet distance is a well-studied distance measure for paths in a metric space. It is mostly studied for paths in -dimensional Euclidean space. Here, computing the Fréchet…
Which Vertical Graphs are Non VPHT Reconstructible?
Jette Gutzeit, Kalani Kistler, Tim Ophelders +1
The verbose persistent homology transform (VPHT) is a topological summary of shapes in Euclidean space. Assuming general position, the VPHT is injective, meaning shapes can be reco…
Reconfiguration of Squares Using a Constant Number of Moves Each
Thijs van der Horst, Maarten Löffler, Tim Ophelders +1
Multi-robot motion planning is a hard problem. We investigate restricted variants of the problem where square robots are allowed to slide over an arbitrary curve to a new position…
Locally Correct Interleavings between Merge Trees
Thijs Beurskens, Tim Ophelders, Bettina Speckmann +1
Temporal sequences of terrains arise in various application areas. To analyze them efficiently, one generally needs a suitable abstraction of the data as well as a method to compar…
Computing the Fréchet Distance When Just One Curve is -Packed: A Simple Almost-Tight Algorithm
Jacobus Conradi, Ivor van der Hoog, Thijs van der Horst +1
We study approximating the continuous Fréchet distance of two curves with complexity and , under the assumption that only one of the two curves is -packed. Driemel, Har{-…
A near-linear time exact algorithm for the -geodesic Fréchet distance between two curves on the boundary of a simple polygon
Thijs van der Horst, Marc van Kreveld, Tim Ophelders +1
Let be a polygon with vertices. Let and be two simple, interior disjoint curves on the boundary of , with and vertices. We show how to compute the Fréche…
ParkView: Visualizing Monotone Interleavings
Thijs Beurskens, Steven van den Broek, Arjen Simons +5
Merge trees are a powerful tool from topological data analysis that is frequently used to analyze scalar fields. The similarity between two merge trees can be captured by an interl…
The Geodesic Fréchet Distance Between Two Curves Bounding a Simple Polygon
Thijs van der Horst, Marc van Kreveld, Tim Ophelders +1
The Fréchet distance is a popular similarity measure that is well-understood for polygonal curves in : near-quadratic time algorithms exist, and conditional lower bou…
Sweeping Orders for Simplicial Complex Reconstruction
Tim Ophelders, Anna Schenfisch
Standard sweep algorithms require an order of discrete points in Euclidean space, and rely on the property that, at a given point, all points in the halfspace below come earlier in…
Faster, Deterministic and Space Efficient Subtrajectory Clustering
Ivor van der Hoog, Thijs van der Horst, Tim Ophelders
Given a trajectory and a distance , we wish to find a set of curves of complexity at most , such that we can cover with subcurves that each are within Fréchet…
The Complexity of Geodesic Spanners using Steiner Points
Sarita de Berg, Tim Ophelders, Irene Parada +2
A geometric -spanner on a set of point sites in a metric space is a subgraph of the complete graph on such that for every pair of sites the d…
Faster Fréchet Distance Approximation through Truncated Smoothing
Thijs van der Horst, Marc van Kreveld, Tim Ophelders +1
The Fréchet distance is a commonly used distance measure for curves. Computing the Fréchet distance between two polygonal curves of vertices takes roughly quadratic time, and c…
Optimal In-Place Compaction of Sliding Cubes
Irina Kostitsyna, Tim Ophelders, Irene Parada +3
The sliding cubes model is a well-established theoretical framework that supports the analysis of reconfiguration algorithms for modular robots consisting of face-connected cubes.…
Relating Interleaving and Fréchet Distances via Ordered Merge Trees
Thijs Beurskens, Tim Ophelders, Bettina Speckmann +1
Merge trees are a common topological descriptor for data with a hierarchical component, such as terrains and scalar fields. The interleaving distance, in turn, is a common distance…
Simply Realising an Imprecise Polyline is NP-hard
Thijs van der Horst, Tim Ophelders, Bart van der Steenhoven
We consider the problem of deciding, given a sequence of regions, if there is a choice of points, one for each region, such that the induced polyline is simple or weakly simple, me…
Shortest Paths in Portalgons
Maarten Löffler, Tim Ophelders, Frank Staals +1
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 fragmen…
Morphing Planar Graph Drawings Through 3D
Kevin Buchin, Will Evans, Fabrizio Frati +4
In this paper, we investigate crossing-free 3D morphs between planar straight-line drawings. We show that, for any two (not necessarily topologically equivalent) planar straight-li…
A Subquadratic -approximation for the Continuous Fréchet Distance
Thijs van der Horst, Marc van Kreveld, Tim Ophelders +1
The Fréchet distance is a commonly used similarity measure between curves. It is known how to compute the continuous Fréchet distance between two polylines with and vertice…
Minimum Height Drawings of Ordered Trees in Polynomial Time: Homotopy Height of Tree Duals
Salman Parsa, Tim Ophelders
We consider drawings of graphs in the plane in which vertices are assigned distinct points in the plane and edges are drawn as simple curves connecting the vertices and such that t…
Efficient Fréchet distance queries for segments
Maike Buchin, Ivor van der Hoog, Tim Ophelders +3
We study the problem of constructing a data structure that can store a two-dimensional polygonal curve , such that for any query segment one can efficiently comp…
Computing the Fréchet Distance Between Uncertain Curves in One Dimension
Kevin Buchin, Maarten Löffler, Tim Ophelders +3
We consider the problem of computing the Fréchet distance between two curves for which the exact locations of the vertices are unknown. Each vertex may be placed in a given uncerta…
Polygon-Universal Graphs
Tim Ophelders, Ignaz Rutter, Bettina Speckmann +1
We study a fundamental question from graph drawing: given a pair of a graph and a cycle in together with a simple polygon , is there a straight-line drawing…
Between Shapes, Using the Hausdorff Distance
Marc van Kreveld, Tillmann Miltzow, Tim Ophelders +2
Given two shapes and in the plane with Hausdorff distance , is there a shape with Hausdorff distance to and from and ? The answer is always yes, and dep…
A family of metrics from the truncated smoothing of Reeb graphs
Erin Wolf Chambers, Elizabeth Munch, Tim Ophelders
In this paper, we introduce an extension of smoothing on Reeb graphs, which we call truncated smoothing; this in turn allows us to define a new family of metrics which generalize t…