Source author record

Luis Barba

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

ResearcherUnclaimed source record

Computational Geometry Data Structures and Algorithms Machine Learning

Catalog footprint

Research overview

15works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Dynamic Model Pruning with Feedback

Deep neural networks often have millions of parameters. This can hinder their deployment to low-end devices, not only due to high memory requirements but also because of increased latency at inference. We propose a novel model compression method that generates a sparse trained model without additional overhead: by allowing (i) dynamic allocation of the sparsity pattern and (ii) incorporating feedback signal to reactivate prematurely pruned weights we obtain a performant sparse model in one single training pass (retraining is not needed, but can further improve the performance). We evaluate our method on CIFAR-10 and ImageNet, and show that the obtained sparse models can reach the state-of-the-art performance of dense models. Moreover, their performance surpasses that of models generated by all previously proposed pruning schemes.

preprint2020arXiv

Time-Space Trade-Offs for Computing Euclidean Minimum Spanning Trees

We present time-space trade-offs for computing the Euclidean minimum spanning tree of a set $S$ of $n$ point-sites in the plane. More precisely, we assume that $S$ resides in a random-access memory that can only be read. The edges of the Euclidean minimum spanning tree $\text{EMST}(S)$ have to be reported sequentially, and they cannot be accessed or modified afterwards. There is a parameter $s \in \{1, \dots, n\}$ so that the algorithm may use $O(s)$ cells of read-write memory (called the workspace) for its computations. Our goal is to find an algorithm that has the best possible running time for any given $s$ between $1$ and $n$ . We show how to compute $\text{EMST}(S)$ in $O\big((n^3/s^2)\log s \big)$ time with $O(s)$ cells of workspace, giving a smooth trade-off between the two best known bounds $O(n^3)$ for $s = 1$ and $O(n \log n)$ for $s = n$ . For this, we run Kruskal's algorithm on the relative neighborhood graph (RNG) of $S$ . It is a classic fact that the minimum spanning tree of $\text{RNG}(S)$ is exactly $\text{EMST}(S)$ . To implement Kruskal's algorithm with $O(s)$ cells of workspace, we define $s$ -nets, a compact representation of planar graphs. This allows us to efficiently maintain and update the components of the current minimum spanning forest as the edges are being inserted.

preprint2016arXiv

Incremental Voronoi Diagrams

We study the amortized number of combinatorial changes (edge insertions and removals) needed to update the graph structure of the Voronoi diagram $\mathcal{V}(S)$ (and several variants thereof) of a set $S$ of $n$ sites in the plane as sites are added. We define a general update operation for planar graphs modeling the incremental construction of several variants of Voronoi diagrams as well as the incremental construction of an intersection of halfspaces in $\mathbb{R}^3$ . We show that the amortized number of edge insertions and removals needed to add a new site is $O(\sqrt{n})$ . A matching $Ω(\sqrt{n})$ combinatorial lower bound is shown, even in the case where the graph of the diagram is a tree. This contrasts with the $O(\log{n})$ upper bound of Aronov et al. (2006) for farthest-point Voronoi diagrams when the points are inserted in order along their convex hull. We present a semi-dynamic data structure that maintains the Voronoi diagram of a set $S$ of $n$ sites in convex position. This structure supports the insertion of a new site $p$ and finds the asymptotically minimal number $K$ of edge insertions and removals needed to obtain the diagram of $S \cup \{p\}$ from the diagram of $S$ , in time $O(K\,\mathrm{polylog}\ n)$ worst case, which is $O(\sqrt{n}\;\mathrm{polylog}\ n)$ amortized by the aforementioned result. The most distinctive feature of this data structure is that the graph of the Voronoi diagram is maintained at all times and can be traversed in the natural way; this contrasts with other known data structures supporting nearest neighbor queries. Our data structure supports general search operations on the current Voronoi diagram, which can, for example, be used to perform point location queries in the cells of the current Voronoi diagram in $O(\log n)$ time, or to determine whether two given sites are neighbors in the Delaunay triangulation.

preprint2015arXiv

A linear-time algorithm for the geodesic center of a simple polygon

Given two points in a simple polygon $P$ of $n$ vertices, its geodesic distance is the length of the shortest path that connects them among all paths that stay within $P$ . The geodesic center of $P$ is the unique point in $P$ that minimizes the largest geodesic distance to all other points of $P$ . In 1989, Pollack, Sharir and Rote [Disc. \& Comput. Geom. 89] showed an $O(n\log n)$ -time algorithm that computes the geodesic center of $P$ . Since then, a longstanding question has been whether this running time can be improved (explicitly posed by Mitchell [Handbook of Computational Geometry, 2000]). In this paper we affirmatively answer this question and present a linear time algorithm to solve this problem.

preprint2014arXiv

Compatible Connectivity-Augmentation of Planar Disconnected Graphs

Motivated by applications to graph morphing, we consider the following \emph{compatible connectivity-augmentation problem}: We are given a labelled $n$ -vertex planar graph, $\mathcal{G}$ , that has $r\ge 2$ connected components, and $k\ge 2$ isomorphic planar straight-line drawings, $G_1,\ldots,G_k$ , of $\mathcal{G}$ . We wish to augment $\mathcal G$ by adding vertices and edges to make it connected in such a way that these vertices and edges can be added to $G_1,\ldots,G_k$ as points and straight-line segments, respectively, to obtain $k$ planar straight-line drawings isomorphic to the augmentation of $\mathcal G$ . We show that adding $Θ(nr^{1-1/k})$ edges and vertices to $\mathcal{G}$ is always sufficient and sometimes necessary to achieve this goal. The upper bound holds for all $r\in\{2,\ldots,n\}$ and $k\ge 2$ and is achievable by an algorithm whose running time is $O(nr^{1-1/k})$ for $k=O(1)$ and whose running time is $O(kn^2)$ for general values of $k$ . The lower bound holds for all $r\in\{2,\ldots,n/4\}$ and $k\ge 2$ .

preprint2014arXiv

Continuous Yao Graphs

In this paper, we introduce a variation of the well-studied Yao graphs. Given a set of points $S\subset \mathbb{R}^2$ and an angle $0 < θ\leq 2π$ , we define the continuous Yao graph $cY(θ)$ with vertex set $S$ and angle $θ$ as follows. For each $p,q\in S$ , we add an edge from $p$ to $q$ in $cY(θ)$ if there exists a cone with apex $p$ and aperture $θ$ such that $q$ is the closest point to $p$ inside this cone. We study the spanning ratio of $cY(θ)$ for different values of $θ$ . Using a new algebraic technique, we show that $cY(θ)$ is a spanner when $θ\leq 2π/3$ . We believe that this technique may be of independent interest. We also show that $cY(π)$ is not a spanner, and that $cY(θ)$ may be disconnected for $θ> π$ .

preprint2014arXiv

Space-Time Trade-offs for Stack-Based Algorithms

In memory-constrained algorithms we have read-only access to the input, and the number of additional variables is limited. In this paper we introduce the compressed stack technique, a method that allows to transform algorithms whose space bottleneck is a stack into memory-constrained algorithms. Given an algorithm \alg\ that runs in O(n) time using $Θ(n)$ variables, we can modify it so that it runs in $O(n^2/s)$ time using a workspace of O(s) variables (for any $s\in o(\log n)$ ) or $O(n\log n/\log p)$ time using $O(p\log n/\log p)$ variables (for any $2\leq p\leq n$ ). We also show how the technique can be applied to solve various geometric problems, namely computing the convex hull of a simple polygon, a triangulation of a monotone polygon, the shortest path between two points inside a monotone polygon, 1-dimensional pyramid approximation of a 1-dimensional vector, and the visibility profile of a point inside a simple polygon. Our approach exceeds or matches the best-known results for these problems in constant-workspace models (when they exist), and gives the first trade-off between the size of the workspace and running time. To the best of our knowledge, this is the first general framework for obtaining memory-constrained algorithms.

preprint2014arXiv

Theta-3 is connected

In this paper, we show that the $θ$ -graph with three cones is connected. We also provide an alternative proof of the connectivity of the Yao graph with three cones.

preprint2014arXiv

Top-Down Skiplists

We describe todolists (top-down skiplists), a variant of skiplists (Pugh 1990) that can execute searches using at most $\log_{2-\varepsilon} n + O(1)$ binary comparisons per search and that have amortized update time $O(\varepsilon^{-1}\log n)$ . A variant of todolists, called working-todolists, can execute a search for any element $x$ using $\log_{2-\varepsilon} w(x) + o(\log w(x))$ binary comparisons and have amortized search time $O(\varepsilon^{-1}\log w(w))$ . Here, $w(x)$ is the "working-set number" of $x$ . No previous data structure is known to achieve a bound better than $4\log_2 w(x)$ comparisons. We show through experiments that, if implemented carefully, todolists are comparable to other common dictionary implementations in terms of insertion times and outperform them in terms of search times.

preprint2013arXiv

Bichromatic compatible matchings

For a set $R$ of $n$ red points and a set $B$ of $n$ blue points, a $BR$ -matching is a non-crossing geometric perfect matching where each segment has one endpoint in $B$ and one in $R$ . Two $BR$ -matchings are compatible if their union is also non-crossing. We prove that, for any two distinct $BR$ -matchings $M$ and $M'$ , there exists a sequence of $BR$ -matchings $M = M_1, ..., M_k = M'$ such that $M_{i-1}$ is compatible with $M_i$ . This implies the connectivity of the compatible bichromatic matching graph containing one node for each bichromatic matching and an edge joining each pair of compatible matchings, thereby answering the open problem posed by Aichholzer et al. in "Compatible matchings for bichromatic plane straight-line graphs"

preprint2013arXiv

Computing a visibility polygon using few variables

We present several algorithms for computing the visibility polygon of a simple polygon $P$ from a viewpoint inside the polygon, when the polygon resides in read-only memory and only few working variables can be used. The first algorithm uses a constant number of variables, and outputs the vertices of the visibility polygon in $O(n\Rout)$ time, where $\Rout$ denotes the number of reflex vertices of $P$ that are part of the output. The next two algorithms use $O(\log \Rin)$ variables, and output the visibility polygon in $O(n\log \Rin)$ randomized expected time or $O(n\log^2 \Rin)$ deterministic time, where $\Rin$ is the number of reflex vertices of $P$ .

preprint2013arXiv

Computing Covers of Plane Forests

Let $ϕ$ be a function that maps any non-empty subset $A$ of $\mathbb{R}^2$ to a non-empty subset $ϕ(A)$ of $\mathbb{R}^2$ . A $ϕ$ -cover of a set $T=\{T_1, T_2, \dots, T_m\}$ of pairwise non-crossing trees in the plane is a set of pairwise disjoint connected regions such that each tree $T_i$ is contained in some region of the cover, and each region of the cover is either (1) $ϕ(T_i)$ for some $i$ , or (2) $ϕ(A \cup B)$ , where $A$ and $B$ are constructed by either (1) or (2), and $A \cap B \neq \emptyset$ . We present two properties for the function $ϕ$ that make the $ϕ$ -cover well-defined. Examples for such functions $ϕ$ are the convex hull and the axis-aligned bounding box. For both of these functions $ϕ$ , we show that the $ϕ$ -cover can be computed in $O(n\log^2n)$ time, where $n$ is the total number of vertices of the trees in $T$ .

preprint2013arXiv

Linear transformation distance for bichromatic matchings

Let $P=B\cup R$ be a set of $2n$ points in general position, where $B$ is a set of $n$ blue points and $R$ a set of $n$ red points. A \emph{ $BR$ -matching} is a plane geometric perfect matching on $P$ such that each edge has one red endpoint and one blue endpoint. Two $BR$ -matchings are compatible if their union is also plane. The \emph{transformation graph of $BR$ -matchings} contains one node for each $BR$ -matching and an edge joining two such nodes if and only if the corresponding two $BR$ -matchings are compatible. In SoCG 2013 it has been shown by Aloupis, Barba, Langerman, and Souvaine that this transformation graph is always connected, but its diameter remained an open question. In this paper we provide an alternative proof for the connectivity of the transformation graph and prove an upper bound of $2n$ for its diameter, which is asymptotically tight.

preprint2013arXiv

On the stretch factor of the Theta-4 graph

In this paper we show that the θ-graph with 4 cones has constant stretch factor, i.e., there is a path between any pair of vertices in this graph whose length is at most a constant times the Euclidean distance between that pair of vertices. This is the last θ-graph for which it was not known whether its stretch factor was bounded.

preprint2012arXiv

Circle separability queries in logarithmic time

Let $P$ be a set of $n$ points in the plane. In this paper we study a new variant of the circular separability problem in which a point set $P$ is preprocessed so that one can quickly answer queries of the following form: Given a geometric object $Q$ , report the minimum circle containing $P$ and exluding $Q$ . Our data structure can be constructed in $O(n\log n)$ time using O(n) space, and can be used to answer the query when $Q$ is either a circle or a convex $m$ -gon in $O(\log n)$ or $O(\log n + \log m)$ time, respectively.

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.

Luis Barba

Research overview

Is this your work?

15 publications

Dynamic Model Pruning with Feedback

Time-Space Trade-Offs for Computing Euclidean Minimum Spanning Trees

Incremental Voronoi Diagrams

A linear-time algorithm for the geodesic center of a simple polygon

Compatible Connectivity-Augmentation of Planar Disconnected Graphs

Continuous Yao Graphs

Space-Time Trade-offs for Stack-Based Algorithms

Theta-3 is connected

Top-Down Skiplists

Bichromatic compatible matchings

Computing a visibility polygon using few variables

Computing Covers of Plane Forests

Linear transformation distance for bichromatic matchings

On the stretch factor of the Theta-4 graph

Circle separability queries in logarithmic time

See the researcher in context

Building this map preview