Source author record

Rinat Ben Avraham

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Geometry

Catalog footprint

Research overview

4works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

The Discrete and Semi-continuous Fréchet Distance with Shortcuts via Approximate Distance Counting and Selection Techniques

The \emph{Fréchet distance} is a well studied similarity measures between curves. The \emph{discrete Fréchet distance} is an analogous similarity measure, defined for a sequence $A$ of $m$ points and a sequence $B$ of $n$ points, where the points are usually sampled from input curves. In this paper we consider a variant, called the \emph{discrete Fréchet distance with shortcuts}, which captures the similarity between (sampled) curves in the presence of outliers. For the \emph{two-sided} case, where shortcuts are allowed in both curves, we give an $O((m^{2/3}n^{2/3}+m+n)\log^3 (m+n))$ -time algorithm for computing this distance. When shortcuts are allowed only in one noise-containing curve, we give an even faster randomized algorithm that runs in $O((m+n)^{6/5+\varepsilon})$ expected time, for any $\varepsilon>0$ . Our techniques are novel and may find further applications. One of the main new technical results is: Given two sets of points $A$ and $B$ and an interval $I$ , we develop an algorithm that decides whether the number of pairs $(x,y)\in A\times B$ whose distance ${\rm dist}(x,y)$ is in $I$ , is less than some given threshold $L$ . The running time of this algorithm decreases as $L$ increases. In case there are more than $L$ pairs of points whose distance is in $I$ , we can get a small sample of pairs that contains a pair at approximate median distance (i.e., we can approximately "bisect" $I$ ). We combine this procedure with additional ideas to search, with a small overhead, for the optimal one-sided Fréchet distance with shortcuts, using a very fast decision procedure. We also show how to apply this technique for approximating distance selection (with respect to rank), and for computing the semi-continuous Fréchet distance with one-sided shortcuts.

preprint2015arXiv

A faster algorithm for the discrete Fréchet distance under translation

The discrete Fréchet distance is a useful similarity measure for comparing two sequences of points $P=(p_1,\ldots, p_m)$ and $Q=(q_1,\ldots,q_n)$ . In many applications, the quality of the matching can be improved if we let $Q$ undergo some transformation relative to $P$ . In this paper we consider the problem of finding a translation of $Q$ that brings the discrete Fréchet distance between $P$ and $Q$ to a minimum. We devise an algorithm that computes the minimum discrete Fréchet distance under translation in $\mathbb{R}^2$ , and runs in $O(m^3n^2(1+\log(n/m))\log(m+n))$ time, assuming $m\leq n$ . This improves a previous algorithm of Jiang et al.~\cite{JXZ08}, which runs in $O(m^3n^3 \log(m + n))$ time.

preprint2012arXiv

Computing the Discrete Fréchet Distance in Subquadratic Time

The Fréchet distance is a similarity measure between two curves $A$ and $B$ : Informally, it is the minimum length of a leash required to connect a dog, constrained to be on $A$ , and its owner, constrained to be on $B$ , as they walk without backtracking along their respective curves from one endpoint to the other. The advantage of this measure on other measures such as the Hausdorff distance is that it takes into account the ordering of the points along the curves. The discrete Fréchet distance replaces the dog and its owner by a pair of frogs that can only reside on $n$ and $m$ specific pebbles on the curves $A$ and $B$ , respectively. These frogs hop from a pebble to the next without backtracking. The discrete Fréchet distance can be computed by a rather straightforward quadratic dynamic programming algorithm. However, despite a considerable amount of work on this problem and its variations, there is no subquadratic algorithm known, even for approximation versions of the problem. In this paper we present a subquadratic algorithm for computing the discrete Fréchet distance between two sequences of points in the plane, of respective lengths $m\le n$ . The algorithm runs in $O(\dfrac{mn\log\log n}{\log n})$ time and uses $O(n+m)$ storage. Our approach uses the geometry of the problem in a subtle way to encode legal positions of the frogs as states of a finite automata.

preprint2010arXiv

The 2-Center Problem in Three Dimensions

Let P be a set of n points in R^3. The 2-center problem for P is to find two congruent balls of minimum radius whose union covers P. We present two randomized algorithms for computing a 2-center of P. The first algorithm runs in O(n^3 log^5 n) expected time, and the second algorithm runs in O((n^2 log^5 n) /(1-r*/r_0)^3) expected time, where r* is the radius of the 2-center balls of P and r_0 is the radius of the smallest enclosing ball of P. The second algorithm is faster than the first one as long as r* is not too close to r_0, which is equivalent to the condition that the centers of the two covering balls be not too close to each other.

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.