BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Tim Ophelders

Tim Ophelders appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Computational GeometryData Structures and Algorithmsmath.DG

Catalog footprint

What is connected

6works
3topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

6 published item(s)

preprint2022arXiv

A Subquadratic $n^ε$-approximation for the Continuous Fréchet Distance

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 $m$ and $n$ vertices in $\mathbb{R}^d$ in $O(mn (\log \log n)^2)$ time; doing so in strongly subquadratic time is a longstanding open problem. Recent conditional lower bounds suggest that it is unlikely that a strongly subquadratic algorithm exists. Moreover, it is unlikely that we can approximate the Fréchet distance to within a factor $3$ in strongly subquadratic time, even if $d=1$. The best current results establish a tradeoff between approximation quality and running time. Specifically, Colombe and Fox (SoCG, 2021) give an $O(α)$-approximate algorithm that runs in $O((n^3 / α^2) \log n)$ time for any $α\in [\sqrt{n}, n]$, assuming $m = n$. In this paper, we improve this result with an $O(α)$-approximate algorithm that runs in $O((n + mn / α) \log^3 n)$ time for any $α\in [1, n]$, assuming $m \leq n$ and constant dimension $d$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Efficient Fréchet distance queries for segments

We study the problem of constructing a data structure that can store a two-dimensional polygonal curve $P$, such that for any query segment $\overline{ab}$ one can efficiently compute the Fréchet distance between $P$ and $\overline{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 $\overline{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 $\overline{ab}$ together with two points $s, t \in P$ (not necessarily vertices), and ask for the Fréchet distance between $\overline{ab}$ and the curve of $P$ in between $s$ and $t$. Using $O(n\log^2n)$ storage, such queries take $O(\log^3 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+\varepsilon}+n^2)$ size data structure, where $k \in [1..n]$ is a parameter the user can choose, and $\varepsilon > 0$ is an arbitrarily small constant, such that given any segment $\overline{ab}$ and two points $s, t \in P$ we can compute the Fréchet distance between $\overline{ab}$ and the curve of $P$ in between $s$ and $t$ in $O((n/k)\log^2n+\log^4 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: we show that we can compute a local $δ$-simplification (with respect to the Fréchet distance) of a polygonal curve in $O(n^{5/2+\varepsilon})$ time, and that we can efficiently find a translation of an arbitrary query segment $\overline{ab}$ that minimizes the Fréchet distance with respect to a subcurve of $P$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Minimum Height Drawings of Ordered Trees in Polynomial Time: Homotopy Height of Tree Duals

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 the edges intersect only at their common endpoints. There is an intuitive quality measure for drawings of a graph that measures the height of a drawing $ϕ: G \rightarrow \mathbb{R}^2$ as follows. For a vertical line $\ell$ in $\mathbb{R}^2$, let the height of $\ell$ be the cardinality of the set $\ell \cap ϕ(G)$. The height of a drawing of $G$ is the maximum height over all vertical lines. In this paper, instead of abstract graphs, we fix a drawing and consider plane graphs. In other words, we are looking for a homeomorphism of the plane that minimizes the height of the resulting drawing. This problem is equivalent to the homotopy height problem in the plane, and the homotopic Fréchet distance problem. These problems were recently shown to lie in NP, but no polynomial-time algorithm or NP-hardness proof has been found since their formulation in 2009. We present the first polynomial-time algorithm for drawing trees with optimal height. This corresponds to a polynomial-time algorithm for the homotopy height where the triangulation has only one vertex (that is, a set of loops incident to a single vertex), so that its dual is a tree.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Between Shapes, Using the Hausdorff Distance

Given two shapes $A$ and $B$ in the plane with Hausdorff distance $1$, is there a shape $S$ with Hausdorff distance $1/2$ to and from $A$ and $B$? The answer is always yes, and depending on convexity of $A$ and/or $B$, $S$ may be convex, connected, or disconnected. We show that our result can be generalised to give an interpolated shape between $A$ and $B$ for any interpolation variable $α$ between $0$ and $1$, and prove that the resulting morph has a bounded rate of change with respect to $α$. Finally, we explore a generalization of the concept of a Hausdorff middle to more than two input sets. We show how to approximate or compute this middle shape, and that the properties relating to the connectedness of the Hausdorff middle extend from the case with two input sets. We also give bounds on the Hausdorff distance between the middle set and the input.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Constructing monotone homotopies and sweepouts

This article investigates when homotopies can be converted to monotone homotopies without increasing the lengths of curves. A monotone homotopy is one which consists of curves which are simple or constant, and in which curves are pairwise disjoint. We show that, if the boundary of a Riemannian disc can be contracted through curves of length less than $L$, then it can also be contracted monotonously through curves of length less than $L$. This proves a conjecture of Chambers and Rotman. Additionally, any sweepout of a Riemannian $2$-sphere through curves of length less than $L$ can be replaced with a monotone sweepout through curves of length less than $L$. Applications of these results are also discussed.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Computing the Similarity Between Moving Curves

In this paper we study similarity measures for moving curves which can, for example, model changing coastlines or retreating glacier termini. Points on a moving curve have two parameters, namely the position along the curve as well as time. We therefore focus on similarity measures for surfaces, specifically the Fréchet distance between surfaces. While the Fréchet distance between surfaces is not even known to be computable, we show for variants arising in the context of moving curves that they are polynomial-time solvable or NP-complete depending on the restrictions imposed on how the moving curves are matched. We achieve the polynomial-time solutions by a novel approach for computing a surface in the so-called free-space diagram based on max-flow min-cut duality.

0 citations0 reviewsNo code linkedOpen access