Source author record

Edgar Chávez

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

ResearcherUnclaimed source record

Computational Geometry Computer Vision Data Structures and Algorithms math.NA

Catalog footprint

Research overview

4works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Proximal Navigation Graphs and t-spanners

Let $(X,\mathbf{d})$ be a metric space, $V\subseteq X$ a finite set, and $E \subseteq V \times V$ . We call the graph $G(E,V)$ a {\em metric} graph if each edge $(u,v) \in E$ has weight $d(u,v)$ . In particular edge $(u,u)$ is in the graph and have distance $0$ . We call $G$ a {\em proximal navigation graph} or $PN$ -graph if for each edge $(u,v) \in E$ either $u=v$ or there is a node $u_1$ such that $(u,u_1) \in E$ and $\mathbf{d}(u,v) > \mathbf{d}(u_1,v)$ . In such graph it is possible to navigate greedily from an arbitrary source node to an arbitrary target node by reducing the distance between the current node and the target node in each step. The complete graph, the Delaunay triangulation and the Half Space Proximal (HSP) graph (defined below in the paper) are examples of $PN$ -graphs. In this paper we study the relationship between $PN$ -graphs and $t$ -spanners and prove that there are $PN$ -graphs that are not $t$ -spanners for any $t$ . On the positive side we give sufficient conditions for a $PN$ -graph to be a $t$ -spanner and prove that any $PN$ -graph over $\mathbb{R}^n$ under the euclidean distance is a $t$ -spanner.

preprint2022arXiv

Quantum jumbled pattern matching

Let $S_1, S_2 \in Σ^*$ strings, we say that $S_1$ {\em jumble match} $S_2$ if they are permutations of each other. Given a text $T$ of size $N$ and a string $S \in Σ^*$ , the problem of \emph{Jumbled Pattern Matching} (JPM) is to determine all substrings in $T$ jumbled matching $S$ . In classical computing, a widespread conjecture is that JPM requires $Ω(N^{2-ε})$ preprocessing time and space for $O(1)$ query time, or $Ω(N^{1-δ})$ query time in the online version, with $ε, δ>0$ . In this paper, we present a quantum algorithm for the online JPM in $O(\sqrt{N})$ time.

preprint2013arXiv

Polygon Matching and Indexing Under Affine Transformations

Given a collection $\{Z_1,Z_2,\ldots,Z_m\}$ of $n$ -sided polygons in the plane and a query polygon $W$ we give algorithms to find all $Z_\ell$ such that $W=f(Z_\ell)$ with $f$ an unknown similarity transformation in time independent of the size of the collection. If $f$ is a known affine transformation, we show how to find all $Z_\ell$ such that $W=f(Z_\ell)$ in $O(n+\log(m))$ time. For a pair $W,W^\prime$ of polygons we can find all the pairs $Z_\ell,Z_{\ell^\prime}$ such that $W=f(Z_\ell)$ and $W^\prime=f(Z_{\ell^\prime})$ for an unknown affine transformation $f$ in $O(m+n)$ time. For the case of triangles we also give bounds for the problem of matching triangles with variable vertices, which is equivalent to affine matching triangles in noisy conditions.

preprint2012arXiv

XFT: An Extension of the Discrete Fractional Fourier Transform

In recent years there has been a growing interest in the fractional Fourier transform driven by its large number of applications. The literature in this field follows two main routes. On the one hand, the areas where the ordinary Fourier transform has been applied are being revisited to use this intermediate time-frequency representation of signals, and on the other hand, fast algorithms for numerical computation of the fractional Fourier transform are devised. In this paper we derive a Gaussian-like quadrature of the continuous fractional Fourier transform. This quadrature is given in terms of the Hermite polynomials and their zeros. By using some asymptotic formulas, we rewrite the quadrature as a chirp-fft-chirp transformation, yielding a fast discretization of the fractional Fourier transform and its inverse in closed form. We extend the range of the fractional Fourier transform by considering arbitrary complex values inside the unitary circle and not only at the boundary. We find that, the chirp-fft-chirp transformation evaluated at z=i, becomes a more accurate version of the fft which can be used for non-periodic functions.

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.