My publications as of 28 October 2021. Also available as plain text.
Implicit gradient alignment in distributed and federated learning.
, , and .
Submitted to AAAI Conference on Artificial Intelligence.
[arXiv] [BibTeXHide BibTeX]
, , and .
Submitted to AAAI Conference on Artificial Intelligence.
[arXiv] [BibTeXHide BibTeX]
@inproceedings{implicitGrad2021,
author={Barba, Luis and Jaggi, Martin and Dandi, Yatin},
title={Implicit Gradient Alignment in Distributed and Federated Learning},
booktitle={AAAI Conference on Artificial Intelligence},
year={2021},
series={AAAI'22}
}
Multilayer lookahead: a nested version of lookahead.
and .
Submitted to AISTATS Conference on Artificial Intelligence and Statistics.
[arXiv] [BibTeXHide BibTeX]
and .
Submitted to AISTATS Conference on Artificial Intelligence and Statistics.
[arXiv] [BibTeXHide BibTeX]
@inproceedings{multilookahead,
author={Barba, Luis and Denys, Pushkin},
title={Multilayer Lookahead: a Nested Version of Lookahead},
booktitle={AISTATS Conference on Artificial Intelligence and Statistics},
year={2021},
series={AISTATS'22}
}
Dynamic model pruning with feedback.
, , , , and .
Published in the of International Conference on Learning Representations 2020.
[arXiv] [BibTeXHide BibTeX]
, , , , and .
Published in the of International Conference on Learning Representations 2020.
[arXiv] [BibTeXHide BibTeX]
@inproceedings{Lin2020Dynamic,
author={Lin, Tao and Stich, Sebastian and Barba, Luis and Dmitriev, Daniil and Jaggi, Martin},
title={Dynamic Model Pruning with Feedback},
booktitle={Proceedings of the of International Conference on Learning Representations 2020},
year={2020},
series={ICLR'20}
}
Geodesic farthest-point voronoi diagram in linear time.
[AbstractHide Abstract]
.
In Proceedings of the 35th Symposium on Computational Geometry, SoCG'19. 2019.
[arXiv] [BibTeXHide BibTeX]
Abstract: Let $P$ be a simple polygon with $n$ vertices.For any two points in $P$, the geodesic distance between them is the length of the shortest path that connects them among all paths contained in $P$.Given a set $S$ of $m$ sites being a subset of the vertices of $P$, we present a randomized algorithm to compute the geodesic farthest-point Voronoi diagram of $S$ in $P$ running in expected $O(n + m)$ time.That is, a partition of $P$ into cells, at most one cell per site, such that every point in a cell has the same farthest site with respect to the geodesic distance.In particular, this algorithm can be extended to run in expected $O(n + m\log m)$ time when $S$ is an arbitrary set of $m$ sites contained in $P$, thereby solving the open problem posed by Mitchell in Chapter 27 of the Handbook of Computational Geometry.
In Proceedings of the 35th Symposium on Computational Geometry, SoCG'19. 2019.
[arXiv] [BibTeXHide BibTeX]
@inproceedings{GeodesicFVDLinear,
author={Barba, Luis},
title={Geodesic farthest-point Voronoi diagram in linear time},
booktitle={Proceedings of the 35th Symposium on Computational Geometry},
year={2019},
series={SoCG'19}
}
Asymmetric convex intersection testing.
[AbstractHide Abstract]
and .
In Proceedings of the 2nd Symposium on Simplicity in Algorithm, SOSA'19. 2019.
[arXiv] [BibTeXHide BibTeX]
Abstract: Let $P \subset \mathbb{R}^d$ be a set of $n$ points and $\mathcal{H}$ a set of $n$ halfspaces in $d$ dimensions.Our goal is to decide whether the intersection of $\mathcal{H}$ and the convex hull of $P$ are disjoint.Even though ACIT is a natural variant of classic LP-type problems that have been studied at length in the literature, and despite its applications in the analysis of high-dimensional data sets, it appears that the problem has not been studied before.We discuss how known approaches can be used to attack the ACIT problem, and we provide a very simple strategy that leads to a deterministic algorithm, linear on $n$ and $m$, whose running time depends reasonably on the dimension $d$.
In Proceedings of the 2nd Symposium on Simplicity in Algorithm, SOSA'19. 2019.
[arXiv] [BibTeXHide BibTeX]
@inproceedings{AsymmetricIntersectionTesting,
author={Barba, Luis and Mulzer, Wolfgang},
title={Asymmetric Convex Intersection Testing},
booktitle={Proceedings of the 2nd Symposium on Simplicity in Algorithm},
year={2019},
series={SOSA'19}
}
Convex hulls in the presence of obstacles.
[AbstractHide Abstract]
, M. Hoffmann, M. Korman, and .
In Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT'18. 2018.
[pdf] [BibTeXHide BibTeX]
Abstract: We study generalizations of convex hulls to polygonal domains with holes.Convexity in Euclidean space is based on the notion of shortest paths, whichare straight-line segments. In a polygonal domain, shortest paths arepolygonal paths called \emph{geodesics}.One possible generalization of convex hull is based on the ``rubber band''conception of the convex hull as a shortest curve that encloses a given set ofsites. However, we show that it is NP-hard to compute such a curve in ageneral polygonal domain. Hence we focus on a different, more directgeneralization of convexity, where a set $X$ is \emph{geodesically convex} ifit contains all geodesics between every pair of points $x,y\in X$. Thecorresponding \emph{geodesic convex hull} presents a few surprises and turns out to behavequite differently compared to the classic Euclidean setting and to thegeodesic hull inside a simple polygon. As a main result, we describe a classof polygonal domains that suffice to represent geodesic convex hullsand characterize which such domains are geodesically convex. Using such arepresentation we present an algorithm to construct the geodesic convex hullof a set of $O(n)$ sites in a polygonal domain with a total of $n$ vertices and$h$ holes in $O(n^3h^{3+\varepsilon})$ time.
In Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT'18. 2018.
[pdf] [BibTeXHide BibTeX]
@inproceedings{GeodesicHullWithHoles,
author={Barba, Luis and Hoffmann, Michael and Korman, Matias and Pilz, Alexander},
title={Convex hulls in the presence of obstacles},
booktitle={Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory},
year={2018},
series={SWAT'18}
}
Time-space trade-offs for computing Euclidean minimum spanning trees.
[AbstractHide Abstract]
, , and .
In Proceedings of the 13th Latin American Theoretical INformatics Symposium, LATIN'18. 2018.
[pdf] [BibTeXHide BibTeX]
Abstract: In the limited-workspace model, we assume that the input of size $n$lies in a random access read-only memory. The output has to be reportedsequentially, and it cannot be accessed or modified.In addition, there is a read-write\emph{workspace} of $O(s)$ words, where $s \in \{1, \dots, n\}$is a given parameter. In a time-space trade-off, weare interested in how the running time of an algorithmimproves as $s$ varies from $1$ to $n$.We present a time-space trade-off for computing the \emph{Euclideanminimum spanning tree} ($\EMST$) of a set $V$ of $n$ sitesin the plane.We present an algorithmthat computes $\EMST(V)$ using $O((n^3/s^2)\log s)$ time and$O(s)$ words of workspace.Our algorithm uses the fact that $\EMST(V)$ is a subgraph of the bounded-degree\emph{relative neighborhood graph} of $V$, and applies Kruskal's MST algorithm on it.To achieve this with limited workspace, we introduce a compact representation ofplanar graphs, called an \emph{$s$-net} which allows us tomanipulate its component structure during the execution of the algorithm.
In Proceedings of the 13th Latin American Theoretical INformatics Symposium, LATIN'18. 2018.
[pdf] [BibTeXHide BibTeX]
@inproceedings{ConstrainedSpaceMST,
author={Banyassady, Bahareh and Barba, Luis and Mulzer, Wolfgang},
title={{T}ime-Space Trade-Offs for Computing {E}uclidean Minimum Spanning Trees},
booktitle={Proceedings of the 13th Latin American Theoretical INformatics Symposium},
year={2018},
series={LATIN'18}
}
Sharing a pizza: bisecting masses with two cuts.
[AbstractHide Abstract]
and .
In Proceedings of the 29th Canadian Conference on Computational Geometry, CCCG'17. July 2017.
[pdf] [BibTeXHide BibTeX]
Abstract: Assume you have a pizza consisting of four ingredients (e.g., bread, tomatoes, cheese and olives) that you want to share with your friend. You want to do this fairly, meaning that you and your friend should get the same amount of each ingredient. How many times do you need to cut the pizza so that this is possible? We will show that two straight cuts always suffice. More formally, we will show the following extension of the well-known Ham-sandwich theorem: Given four mass distributions in the plane, they can be simultaneously bisected with two lines. That is, there exist two oriented lines with the following property: let $R^+_1$ be the region of the plane that lies to the positive side of both lines and let $R^+_2$ be the region of the plane that lies to the negative side of both lines. Then $R^+=R^+_1\cup R^+_2$ contains exactly half of each mass distribution. Additionally, we prove that five mass distributions in~$\mathbb{R}^3$ can be simultaneously bisected by two planes.
In Proceedings of the 29th Canadian Conference on Computational Geometry, CCCG'17. July 2017.
[pdf] [BibTeXHide BibTeX]
@inproceedings{PizzaCuttings,
author={Barba, Luis and Schnider, Patrick},
title={Sharing a pizza: bisecting masses with two cuts},
booktitle={Proceedings of the 29th Canadian Conference on Computational Geometry},
year={2017},
series={CCCG'17},
month={July}
}
Subquadratic algorithms for algebraic generalizations of 3SUM.
[AbstractHide Abstract]
, , , S. Langerman, , and .
In Proceedings of the 33th Symposium on Computational Geometry, SoCG'17. 2017.
[arXiv] [BibTeXHide BibTeX]
Abstract: The 3SUM problem asks if an input $n$-set of real numbers contains a triple whose sum is zero. We consider the 3POL problem, a natural generalization of 3SUM where we replace the sum function by a constant-degree polynomial in three variables. The motivations are threefold. Raz, Sharir, and de Zeeuw gave an $O(n^{11/6})$ upper bound on the number of solutions of trivariate polynomial equations when the solutions are taken from the cartesian product of three $n$-sets of real numbers. We give algorithms for the corresponding problem of counting such solutions. Gr\o nlund and Pettie recently designed subquadratic algorithms for 3SUM. We generalize their results to 3POL. Finally, we shed light on the General Position Testing~(GPT) problem: ``Given $n$ points in the plane, do three of them lie on a line?'', a key problem in computational geometry.We prove that there exist bounded-degree algebraic decision trees of depth $O(n^{\frac{12}{7}+\varepsilon})$ that solve 3POL, and that 3POL can be solved in $O(n^2 {(\log \log n)}^\frac{3}{2} / {(\log n)}^\frac{1}{2})$ time in the real-RAM model. Among the possible applications of those results, we show how to solve GPT in subquadratic time when the input points lie on $o({(\log n)}^\frac{1}{6}/{(\log\log n)}^\frac{1}{2})$ constant-degree polynomial curves. This constitutes the first step towards closing the major open question of whether GPT can be solved in subquadratic time.To obtain these results, we generalize important tools --- such as batch range searching and dominance reporting --- to a polynomial setting. We expect these new tools to be useful in other applications.
In Proceedings of the 33th Symposium on Computational Geometry, SoCG'17. 2017.
[arXiv] [BibTeXHide BibTeX]
@inproceedings{3POL,
author={Barba, Luis and Cardinal, Jean and Iacono, John and Langerman, Stefan and Ooms, Aur\'elien and Solomon, Noam},
title={{S}ubquadratic Algorithms for Algebraic Generalizations of 3{S}{U}{M}},
booktitle={Proceedings of the 33th Symposium on Computational Geometry},
year={2017},
series={SoCG'17}
}
Dynamic graph coloring.
[AbstractHide Abstract]
, , M. Korman, S. Langerman, A. van Renssen, , and S. Verdonschot.
In Proceedings of the 16th Algorithms and Data Structures Symposium. 2017.
[arXiv] [BibTeXHide BibTeX]
Abstract: In this paper we study the number of vertex recolorings that an algorithm needs to perform in order to maintain a proper coloring of a $c$-colorable graphunder insertion and deletion of vertices and edges.We assume that all updates keep the graph $c$-colorable and that $N$ is the maximum number of vertices in the graph at any point in time.We present two algorithms to maintain an approximation of the optimal coloring that, together, present a trade-off between the number of recolorings and the number of colors used:For any $d>0$, the first algorithm maintains a proper $O(c d N^{1/d})$-coloring and recolors at most $O(d)$ vertices per update.The second maintains an $O(c d)$-coloring using $O(dN^{1/d})$ recolorings per update. Both algorithms achieve the same asymptotic performance when $d = \log N$.Moreover, we show that for any algorithm that maintains a $c$-coloring of a $2$-colorable graph on $N$ vertices during a sequence of $m$ updates, there is a sequence of updates that forces the algorithm to recolor at least $\Omega(m\cdot N^\frac{2}{c(c-1)})$ vertices.
In Proceedings of the 16th Algorithms and Data Structures Symposium. 2017.
[arXiv] [BibTeXHide BibTeX]
@inproceedings{DynamicColoring,
author={Barba, Luis and Cardinal, Jean and Korman, Matias and Langerman, Stefan and van Renssen, Andr\'e and Roeloffzen, Marcel and Verdonschot, Sander},
title={Dynamic Graph Coloring},
booktitle={Proceedings of the 16th Algorithms and Data Structures Symposium},
year={2017}
}
Deterministic algorithms for unique sink orientations of grids.
[AbstractHide Abstract]
, , , and .
In Proceedings of the 22nd International Computing and Combinatorics Conference. 2016.
[BibTeXHide BibTeX]
Abstract: We study Unique Sink Orientations (USOs) of grids: Cartesian products of\emph{two} complete graphs on $n$ vertices, where the edges are oriented in such a way that each subgrid has a unique sink.We consider two different oracle models, the \emph{edge query} and the\emph{vertex query} model.An edge query provides the orientation of the queried edge, whereas a vertex query provides the orientation of all edges incident to the queried vertex.We are interested in bounding the number of queries to the oracle needed by an algorithm to find the sink.In the randomized setting, the best known algorithms find the sink using either $\Theta(n)$ edge queries, or $O(\log^2 n)$ vertex queries, in expectation. We prove that $O(n^{\log_4 7})$ edge queries and $O(n \log n)$ vertex queries suffice to find the sink in the deterministic setting. A deterministic lower bound for both models is $\Omega(n)$.Grid USOs are instances of LP-type problems and violator spaces for which derandomizations of known algorithms remain elusive.
In Proceedings of the 22nd International Computing and Combinatorics Conference. 2016.
[BibTeXHide BibTeX]
@inproceedings{gridUSO,
author={Barba, Luis and Milatz, Malte and Nummenpalo, Jerri and Thomas, Antonis},
title={Deterministic Algorithms for Unique Sink Orientations of Grids},
booktitle={Proceedings of the 22nd International Computing and Combinatorics Conference},
year={2016}
}
The farthest-point geodesic Voronoi diagram of points on the boundary of a simple polygon.
[AbstractHide Abstract]
, , and .
In Proceedings of the 32st Symposium on Computational Geometry. 2016.
[pdf] [BibTeXHide BibTeX]
Abstract: Given a set of sites (points) in a simple polygon, the farthest-pointgeodesic Voronoi diagram partitions the polygon into cells, at mostone cell per site, such that every point in a cell has the samefarthest site with respect to the geodesic metric. We present an$O((n+m) \log\log n)$-time algorithm to compute thefarthest-point geodesic Voronoi diagram for $m$ sites lying onthe boundary of a simple $n$-gon.
In Proceedings of the 32st Symposium on Computational Geometry. 2016.
[pdf] [BibTeXHide BibTeX]
@inproceedings{GeodesicVoronoi,
author={Ahn, Hee-Kap and Barba, Luis and Oh, Eunjin},
title={{T}he farthest-point geodesic {V}oronoi diagram of points on the boundary of a simple polygon},
booktitle={Proceedings of the 32st Symposium on Computational Geometry},
year={2016}
}
Incremental Voronoi diagrams.
[AbstractHide Abstract]
, , , and S. Langerman.
In Proceedings of the 32st Symposium on Computational Geometry. 2016.
[BibTeXHide BibTeX]
Abstract: We study the amortized number of combinatorial changes (edge insertions and removals) needed to update the graph structure of the Voronoi diagram $\VD(S)$ (and several variants thereof) of a set $S$ of $n$ sites in the plane as sites are added to the set.To that effect, we define a general update operation for planar graphs that can be used to model 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 to the Voronoi diagram is $O(\sqrt{n})$.A matching $\Omega(\sqrt{n})$ combinatorial lower bound is shown, even in the case where the graph representing the Voronoi diagram is a tree.This contrasts with the $O(\log{n})$ upper bound of Aronov et al.~(2006) for farthest-point Voronoi diagrams in the special case where the points are inserted in clockwise order along their convex hull.We then present a semi-dynamic data structure that maintains the Voronoi diagram of a set $S$ of $n$ sites in convex position.This data structure supports the insertion of a new site $p$ (and hence the addition of its Voronoi cell) 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 combinatorial result.The most distinctive feature of this data structure is that the graph of the Voronoi diagram is maintained explicitly at all times and can be retrieved and traversed in the natural way; this contrasts with other structures supporting nearest neighbor queries in that they do not maintain the Voronoi diagram after each insertion.This 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.
In Proceedings of the 32st Symposium on Computational Geometry. 2016.
[BibTeXHide BibTeX]
@inproceedings{IncrementalVoronoi,
author={Allen, Sarah and Barba, Luis and Iacono, John and Langerman, Stefan},
title={{I}ncremental {V}oronoi diagrams},
booktitle={Proceedings of the 32st Symposium on Computational Geometry},
year={2016}
}
A Linear-Time Algorithm for the Geodesic Center of a Simple Polygon.
[AbstractHide Abstract]
, , P. Bose, J. de Carufel, M. Korman, and .
In Proceedings of the 31st Symposium on Computational Geometry, volume 34, pages 209–223, 2015.
[pdf] [arXiv] [BibTeXHide BibTeX]
Abstract: Let $P$ be a closed simple polygon with $n$ vertices.For any two points in $P$, the geodesic distance between them is the length of the shortest path that connects them among all paths contained in $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.In this paper we affirmatively answer this question and present a linear time algorithm to solve this problem.
In Proceedings of the 31st Symposium on Computational Geometry, volume 34, pages 209–223, 2015.
[pdf] [arXiv] [BibTeXHide BibTeX]
@inproceedings{GeodesicCenter,
author={Ahn, Hee-Kap and Barba, Luis and Bose, Prosenjit and de Carufel, Jean-Lou and Korman, Matias and Oh, Eunjin},
title={{A Linear-Time Algorithm for the Geodesic Center of a Simple Polygon}},
booktitle={Proceedings of the 31st Symposium on Computational Geometry},
year={2015},
volume={34},
pages={209-223}
}
Column planarity and partial simultaneous geometric embedding for outerplanar graphs.
[AbstractHide Abstract]
, M. Hoffmann, and V. Kusters.
In Proceedings of the European Workshop on Computational Geometry, EuroCG'15. 2015.
[BibTeXHide BibTeX]
Abstract: Given a graph $G=(V,E)$, a set $R\subseteq V$ is \defn{column planar} in $G$if we can assign $x$-coordinates to the vertices in $R$ such that everyassignment of $y$-coordinates to $R$ gives a partial embedding of $G$ thatcan be completed to a plane straight-line embedding of the whole graph. Thisnotion is strongly related to unlabeled level planarity. We prove that everyouterplanar graph on $n$ vertices contains a column planar set of size atleast~$n/2$.We use this result to show that every pair of outerplanar graphs $G_1$ and $G_2$on the same set $V$ of $n$ vertices admit an $(n/4)$-\defn{partialsimultaneous geometric embedding} (PSGE): a plane straight-line embedding of$G_1$ and a plane straight-line embedding of $G_2$ such that $n/4$ verticesare mapped to the same point in the two drawings. This is a relaxation of thewell-studied notion of \defn{simultaneous geometric embedding}, which isequivalent to $n$-PSGE.
In Proceedings of the European Workshop on Computational Geometry, EuroCG'15. 2015.
[BibTeXHide BibTeX]
@inproceedings{barbacolumn,
author={Barba, Luis and Hoffmann, Michael and Kusters, Vincent},
title={Column Planarity and Partial Simultaneous Geometric Embedding for Outerplanar Graphs},
booktitle={Proceedings of the European Workshop on Computational Geometry},
year={2015},
series={EuroCG'15}
}
Compatible connectivity-augmentation of planar disconnected graphs.
[AbstractHide Abstract]
G. Aloupis, , , , , and P. Morin.
In Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms, pages 1602–1615, 2015.
[pdf] [arXiv] [BibTeXHide BibTeX]
Abstract: Motivated by applications to graph morphing, we consider the following\emph{compatible connectivity-augmentation problem}: We are givena 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 thatthese vertices and edges can be added to $G_1,\ldots,G_k$ as points andstraight-line segments, respectively, to obtain $k$ planar straight-linedrawings isomorphic to the augmentation of $\mathcal G$. We showthat adding $\Theta(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 isachievable 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$.
In Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms, pages 1602–1615, 2015.
[pdf] [arXiv] [BibTeXHide BibTeX]
@inproceedings{CompatibleEmbeddings,
author={Aloupis, Greg and Barba, Luis and Carmi, Paz and Dujmovi\'c, Vida and Frati, Fabrizio and Morin, Pat},
title={Compatible Connectivity-Augmentation of Planar Disconnected Graphs},
booktitle={Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms},
year={2015},
pages={1602-1615}
}
Optimal detection of intersections between convex polyhedra.
[AbstractHide Abstract]
and S. Langerman.
In Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms, pages 1641–1654, 2015.
[pdf] [arXiv] [BibTeXHide BibTeX]
Abstract: For a polyhedron $P$ in $\mathbb{R}^d$, denote by $|P|$ its combinatorial complexity, i.e.,the number of faces of all dimensions of the polyhedra.In this paper, we revisit the classic problem of preprocessingpolyhedra independently so that given two preprocessed polyhedra $P$and $Q$ in $\mathbb{R}^d$, each translated and rotated, theirintersection can be tested rapidly.For $d=3$ we show how to perform such a test in$O(\log |P| + \log |Q|)$ timeafter linear preprocessing time and space. This running time is the best possible and improves upon the lastbest known query time of $O(\log|P| \log|Q|)$ by Dobkin and Kirkpatrick (1990).We then generalize our method to any constant dimension $d$, achieving the same optimal$O(\log |P| + \log |Q|)$ query time using a representation of size$O(|P|^{\lfloor d/2\rfloor + \varepsilon})$ for any $\varepsilon>0$ arbitrarily small.This answers an even older question posed by Dobkin and Kirkpatrick 30years ago.In addition, we provide an alternative $O(\log |P| + \log |Q|)$algorithm to test the intersection of two convex polygons $P$ and $Q$ in the plane.
In Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms, pages 1641–1654, 2015.
[pdf] [arXiv] [BibTeXHide BibTeX]
@inproceedings{barba2013detecting,
author={Barba, Luis and Langerman, Stefan},
title={Optimal detection of intersections between convex polyhedra},
booktitle={Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms},
year={2015},
pages={1641-1654}
}
Drawing the Horton set in an integer grid of minimun size.
[AbstractHide Abstract]
, , R. Fabila-Monroy, and .
In Proceedings of the 26th Canadian Conference on Computational Geometry, CCCG'14. August 2014.
[pdf] [BibTeXHide BibTeX]
Abstract: In this paper we show that the Horton set of $n$ points can be realized withinteger coordinates of absolute value at most $\frac{1}{2}n^{\frac{\log(n)-1}{2}}$.We also show that any set of points with integer coordinatesthat has the same order type as the Horton set contains point witha coordinate of absolute value at least $(n/2)^{\frac{\log (n)-1}{32}}$.
In Proceedings of the 26th Canadian Conference on Computational Geometry, CCCG'14. August 2014.
[pdf] [BibTeXHide BibTeX]
@inproceedings{HortonSet,
author={Barba, Luis and Duque, Frank and Fabila-Monroy, R and Hidalgo-Toscano, Carlos},
title={{D}rawing the {H}orton Set in an Integer Grid of Minimun Size},
booktitle={Proceedings of the 26th Canadian Conference on Computational Geometry},
year={2014},
series={CCCG'14},
month={August}
}
Continuous Yao graphs.
[AbstractHide Abstract]
, P. Bose, J. de Carufel, , , A. van Renssen, P. Taslakian, and S. Verdonschot.
In Proceedings of the 26th Canadian Conference on Computational Geometry, CCCG'14. August 2014.
[pdf] [arXiv] [BibTeXHide BibTeX]
Abstract: 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 < \theta \leq 2\pi$,we define the \emph{continuous Yao graph} $\cyao$ with vertex set $S$ and angle $\theta$ as follows. For each $p,q\in S$, we add an edge from $p$ to $q$ in $\cyao$if there exists a cone with apex $p$ and aperture $\theta$ such that $q$ is the closest point to $p$ inside this cone.We study the spanning ratio of \cyao for different values of $\theta$.Using a new algebraic technique, we show that $\cyao$ is a spanner when $\theta \leq 2\pi /3$. We believe that this technique may be of independent interest. We also show that $\cyaopi$ is not a spanner, and that $\cyao$ may be disconnected for $\theta > \pi$.
In Proceedings of the 26th Canadian Conference on Computational Geometry, CCCG'14. August 2014.
[pdf] [arXiv] [BibTeXHide BibTeX]
@inproceedings{ContinuousYao,
author={Barba, Luis and Bose, Prosenjit and de Carufel, Jean-Lou and Damian, Mirela and Fagerberg, Rolf and van Renssen, Andr\'e and Taslakian, Perouz and Verdonschot, Sander},
title={{C}ontinuous {Y}ao Graphs},
booktitle={Proceedings of the 26th Canadian Conference on Computational Geometry},
year={2014},
series={CCCG'14},
month={August}
}
Linear transformation distance for bichromatic matchings.
[AbstractHide Abstract]
O. Aichholzer, , T. Hackl, , and B. Vogtenhuber.
In Proceedings of the 30th Symposium on Computational Geometry, SoCG'14, page 154, 2014.
[pdf] [arXiv] [BibTeXHide BibTeX]
Abstract: 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.
In Proceedings of the 30th Symposium on Computational Geometry, SoCG'14, page 154, 2014.
[pdf] [arXiv] [BibTeXHide BibTeX]
@inproceedings{BichromaticDistance,
author={Aichholzer, Oswin and Barba, Luis and Hackl, Thomas and Pilz, Alexander and Vogtenhuber, Birgit},
title={Linear transformation distance for bichromatic matchings},
booktitle={Proceedings of the 30th Symposium on Computational Geometry},
year={2014},
series={SoCG'14},
pages={154}
}
Weight balancing on boundaries and skeletons.
[AbstractHide Abstract]
, J. de Carufel, , , , , M. Korman, , , , , S. Verdonschot, and .
In Proceedings of the 30th Symposium on Computational Geometry, SoCG'14. 2014.
[pdf] [BibTeXHide BibTeX]
Abstract: We consider the problem of finding a location (called balancing location) for a set of points on the boundary of a region so that their ``center of mass'' coincides with a target point $p$ in the region. In the particular case where we want to locate two points of the same weight, we are effectively trying to find an antipodal pair with respect to $p$. We consider several variations of the problem and give criteria that ensure the existence of a balancing set. In particular, we show the following results. (1) In the plane, if the largest weight is at most the sum of the other weights, there exists a balancing location on the boundary of any closed bounded region, for any $p$ inside the region. If the weights do not satisfy this condition, we present a region and a target point for which this is not possible. (2) In the 3-dimensional space, there always exist three points on the boundary of a 3-dimensional polyhedral region so that they form an equilateral triangle with the center at $p$. (3) In the 3-dimensional space, there always exist three points on the 1-skeleton of a 3-dimensional convex polyhedral region so that their center of mass coincides with $p$.
In Proceedings of the 30th Symposium on Computational Geometry, SoCG'14. 2014.
[pdf] [BibTeXHide BibTeX]
@inproceedings{barba2014inverse,
author={Barba, Luis and de Carufel, Jean-Lou and Cheong, Otfried and Dobbins, Michael and Fleischer, Rudolf and Kawamura, Akitoshi and Korman, Matias and Okamoto, Yoshio and Pach, J\'anos and Tang, Yuan and Tokuyama, Takeshi and Verdonschot, Sander and Wang, Tianhao},
title={Weight Balancing on Boundaries and Skeletons},
booktitle={Proceedings of the 30th Symposium on Computational Geometry},
year={2014},
series={SoCG'14}
}
New and improved spanning ratios for Yao graphs.
[AbstractHide Abstract]
, P. Bose, , , , , A. van Renssen, P. Taslakian, S. Verdonschot, and .
In Proceedings of the 30th Symposium on Computational Geometry, SoCG'14. 2014.
[pdf] [BibTeXHide BibTeX]
Abstract: For a set of points in the plane and a fixed integer $k > 0$, the Yao graph $Y_k$ partitions the space around each point into $k$ equiangular cones of angle $\theta=2\pi/k$, and connects each point to a nearest neighbor in each cone. It is known for all Yao graphs, with the sole exception of $Y_5$, whether or not they are geometric spanners. In this paper we close this gap by showing that for odd $k \geq 5$, the spanning ratio of $Y_k$ is at most $1/(1-2\sin(3\theta/8))$, which gives the first constant upper bound for $Y_5$, and is an improvement over the previous bound of $1/(1-2\sin(\theta/2))$ for odd $k \geq 7$. We further reduce the upper bound on the spanning ratio for $Y_5$ from $10.9$ to $2+\sqrt{3} \approx 3.74$, which falls slightly below the lower bound of $3.79$ established for the spanning ratio of $\Theta_5$ ($\Theta$-graphs differ from Yao graphs only in the way they select the closest neighbor in each cone). This is the first such separation between a Yao and $\Theta$-graph with the same number of cones. We also give a lower bound of $2.87$ on the spanning ratio of $Y_5$. Finally, we revisit the $Y_6$ graph, which plays a particularly important role as the transition between the graphs ($k > 6$) for which simple inductive proofs are known, and the graphs ($k \le 6$) whose best spanning ratios have been established by complex arguments. Here we reduce the known spanning ratio of $Y_6$ from $17.6$ to $5.8$, getting closer to the spanning ratio of 2 established for $\Theta_6$.
In Proceedings of the 30th Symposium on Computational Geometry, SoCG'14. 2014.
[pdf] [BibTeXHide BibTeX]
@inproceedings{barba2014new,
author={Barba, Luis and Bose, Prosenjit and Damian, Mirela and Fagerberg, Rolf and Keng, Wah Loon and O'Rourke, Joseph and van Renssen, Andr\'e and Taslakian, Perouz and Verdonschot, Sander and Xia, Ge},
title={{N}ew and Improved Spanning Ratios for {Y}ao Graphs},
booktitle={Proceedings of the 30th Symposium on Computational Geometry},
year={2014},
series={SoCG'14}
}
Optimal algorithms for constrained 1-center problems.
[AbstractHide Abstract]
, P. Bose, and S. Langerman.
In Proceedings of the 11th Latin American Theoretical INformatics Symposium, LATIN'14, pages (84–95), March 2014.
[pdf] [BibTeXHide BibTeX]
Abstract: In this paper we address the following problem: Given a set $P$ of $n$ points in the plane, find the minimum enclosing circle of $P$ whose center is constrained to lie on a given subset $\Phi$ of the plane. We study the case where $\Phi$ is either a set of points, a set of segments (lines) or a simple polygon.We propose two algorithms, the first one solves the problem when the center is constrained to lie on a set of $m$ segments and runs in expected $O((n+m)\log \omega)$ time where $\omega = \min\{n,m\}$. This algorithm can be applied when the center is constrained to lie on sets of points or a set of simple polygons.Surprisingly, when constraining the center to lie inside a simple polygon on $m$ vertices we can improve the running time to $\Theta(m + n\log n)$ whenever $m\geq n$. Both algorithms provide significant improvements when $n$ and $m$ differ widely.We provide matching lower bounds for both algorithms in the algebraic computation tree model.While proving these results, we obtained an $\Omega(n \log m)$ lower bound for the following problem: Given two sets $A$ and $B$ in $\mathbb{R}$ of size $m$ and $n$, respectively, is $A \subseteq B$?
In Proceedings of the 11th Latin American Theoretical INformatics Symposium, LATIN'14, pages (84–95), March 2014.
[pdf] [BibTeXHide BibTeX]
@inproceedings{ConstrainedMEC,
author={Barba, Luis and Bose, Prosenjit and Langerman, Stefan},
title={Optimal algorithms for constrained 1-center problems},
booktitle={Proceedings of the 11th Latin American Theoretical INformatics Symposium},
year={2014},
series={LATIN'14},
pages={(84-95)},
month={March}
}
Isoperimetric enclosures.
[AbstractHide Abstract]
G. Aloupis, , J. de Carufel, S. Langerman, and D. Souvaine.
In Proceedings of the 1st Mexican Conference on Discrete Mathematics and Computational Geometry, MCDMCG'13, pages 47–56, November 2013.
[pdf] [BibTeXHide BibTeX]
Abstract: Let $S$ be a set of $n>2$ points in the plane whose convex hull has perimeter $t$.Given a number $P\geq t$, we study the following problem: Of all curves of perimeter $P$ that enclose $S$, which is the curve that encloses the maximum area? In this paper, we give a complete characterization of this curve.We show that there are cases where this curve cannot be computed exactly and provide an~$O(n\log n)$-time algorithm to obtain an approximation of this curve, with arbitrary precision, having the same combinatorial structure.
In Proceedings of the 1st Mexican Conference on Discrete Mathematics and Computational Geometry, MCDMCG'13, pages 47–56, November 2013.
[pdf] [BibTeXHide BibTeX]
@inproceedings{IsoperimetricEnclosures,
author={Aloupis, Greg and Barba, Luis and de Carufel, Jean-Lou and Langerman, Stefan and Souvaine, Diane L.},
title={Isoperimetric Enclosures},
booktitle={Proceedings of the 1st Mexican Conference on Discrete Mathematics and Computational Geometry},
year={2013},
series={MCDMCG'13},
pages={47-56},
month={November}
}
Theta-3 is connected.
[AbstractHide Abstract]
O. Aichholzer, , , P. Bose, M. Korman, A. van Renssen, P. Taslakian, and S. Verdonschot.
In Proceedings of the 25th Canadian Conference on Computational Geometry, CCCG'13, pages 205–210, August 2013.
[pdf] [BibTeXHide BibTeX]
Abstract: In this paper, we show that the $\theta$-graph with three cones is connected.We also provide an alternative proof of the connectivity of the Yao-graph with three cones.
In Proceedings of the 25th Canadian Conference on Computational Geometry, CCCG'13, pages 205–210, August 2013.
[pdf] [BibTeXHide BibTeX]
@inproceedings{Theta3,
author={Aichholzer, Oswin and Bae, Sang Won and Barba, Luis and Bose, Prosenjit and Korman, Matias and van Renssen, Andr\'e and Taslakian, Perouz and Verdonschot, Sander},
title={Theta-3 is connected},
booktitle={Proceedings of the 25th Canadian Conference on Computational Geometry},
year={2013},
series={CCCG'13},
pages={205-210},
month={August}
}
Computing covers of plane forests.
[AbstractHide Abstract]
, , P. Bose, and .
In Proceedings of the 25th Canadian Conference on Computational Geometry, CCCG'13, pages 217–222, August 2013.
[pdf] [BibTeXHide BibTeX]
Abstract: Let $\phi$ be a function that maps any non-empty subset $A$ of$\mathbb{R}^2$ to a non-empty subset $\phi(A)$ of $\mathbb{R}^2$. A $\phi$-cover ofa set $T=\{T_1, T_2, \dots, T_m\}$ of pairwise non-crossing treesin the plane is a set of pairwise disjoint connected regions such that:$(1.)$ each tree $T_i$ is contained in some region of the cover,$(2.)$ each region of the cover is either $(a)$ $\phi(T_i)$ for some $i$, or $(b)$$\phi(A \cup B)$, where $A$ and $B$ are constructed by either $2a$ or $2b$, and $A \cap B \neq \emptyset$.We present two properties for the function $\phi$ that make the $\phi$-cover well-defined. Examples for such functions $\phi$ are the convex hull and the axis-aligned bounding box. For both of these functions $\phi$, we show that the $\phi$-cover can be computed in $O(n\log^2n)$ time, where $n$ is the total number of vertices of the trees in $T$.
In Proceedings of the 25th Canadian Conference on Computational Geometry, CCCG'13, pages 217–222, August 2013.
[pdf] [BibTeXHide BibTeX]
@inproceedings{ForestCovers,
author={Barba, Luis and Beingessner, Alexis and Bose, Prosenjit and Smid, Michiel},
title={Computing Covers of Plane Forests},
booktitle={Proceedings of the 25th Canadian Conference on Computational Geometry},
year={2013},
series={CCCG'13},
pages={217-222},
month={August}
}
On $k$-enclosing objects in a coloured point set.
[AbstractHide Abstract]
, , , , , , , , and .
In Proceedings of the 25th Canadian Conference on Computational Geometry, CCCG'13, pages 229–234, August 2013.
[pdf] [BibTeXHide BibTeX]
Abstract: Given a set $P$ of $n$ points in $\mathbb{R}^2$, each of which has an associated colour in $\{1, \ldots, t\}$, and a vector $V=(c_1,\ldots,c_t)$, where $c_i\in \mathbb{Z}^+$ for each $1\le i\le t$, an exact coloured $k$-enclosing object is a region in $\mathbb{R}^2$ that contains exactly $c_i$ points of $P$ of colour $i$ for each $i$. We examine the problems of finding exact coloured $k$-enclosing axis-aligned rectangles, squares, discs, and two-sided dominating regions in a $t$-coloured point set.
In Proceedings of the 25th Canadian Conference on Computational Geometry, CCCG'13, pages 229–234, August 2013.
[pdf] [BibTeXHide BibTeX]
@inproceedings{EnclosingObjectsInColouredPointSet,
author={Barba, Luis and Durocher, Stephane and Fraser, Robert and Hurtado, Ferran and Mehrabi, Saeed and Mondal, Debajyoti and Morrison, Jason and Skala, Matthew and Wahid, Mohammad Abdul},
title={On $k$-Enclosing Objects in a Coloured Point Set},
booktitle={Proceedings of the 25th Canadian Conference on Computational Geometry},
year={2013},
series={CCCG'13},
pages={229-234},
month={August}
}
On the stretch factor of the Theta-4 graph.
[AbstractHide Abstract]
, P. Bose, J. de Carufel, A. van Renssen, and S. Verdonschot.
In Proceedings of the 13th Algorithms and Data Structures Symposium, WADS'13, pages 109–120, August 2013.
[pdf] [arXiv] [BibTeXHide BibTeX]
Abstract: In this paper we show that the $\theta$-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 $\theta$-graph for which it was not known whether its stretch factor was bounded.
In Proceedings of the 13th Algorithms and Data Structures Symposium, WADS'13, pages 109–120, August 2013.
[pdf] [arXiv] [BibTeXHide BibTeX]
@inproceedings{Theta4,
author={Barba, Luis and Bose, Prosenjit and de Carufel, Jean-Lou and van Renssen, Andr\'e and Verdonschot, Sander},
title={{O}n the stretch factor of the {T}heta-4 graph},
booktitle={Proceedings of the 13th Algorithms and Data Structures Symposium},
year={2013},
series={WADS'13},
pages={109-120},
month={August}
}
Bichromatic compatible matchings.
[AbstractHide Abstract]
G. Aloupis, , S. Langerman, and D. Souvaine.
In Proceedings of the 29th Symposium on Computational Geometry, SoCG'13, pages 267–276, June 2013.
[pdf] [arXiv] [BibTeXHide BibTeX]
Abstract: For a set $R$ of $n$ red points and a set $B$ of$n$ blue points, a $BR$-matching is anon-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 , \ldots, 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
In Proceedings of the 29th Symposium on Computational Geometry, SoCG'13, pages 267–276, June 2013.
[pdf] [arXiv] [BibTeXHide BibTeX]
@inproceedings{BichromaticMatchings,
author={Aloupis, Greg and Barba, Luis and Langerman, Stefan and Souvaine, Diane L.},
title={Bichromatic compatible matchings},
booktitle={Proceedings of the 29th Symposium on Computational Geometry},
year={2013},
series={SoCG'13},
pages={267-276},
month={June}
}
Space-time trade-offs for stack-based algorithms.
[AbstractHide Abstract]
, M. Korman, S. Langerman, , and R. Silveira.
In Proceedings of the 30th Symposium on Theoretical Aspects of Computer Science, STACS'13, pages 281–292, February-March 2013.
[pdf] [arXiv] [BibTeXHide BibTeX]
Abstract: 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 a stack of length $\Theta(n)$, we can modify it so that it runs in $O(n^2/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 a 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.
In Proceedings of the 30th Symposium on Theoretical Aspects of Computer Science, STACS'13, pages 281–292, February-March 2013.
[pdf] [arXiv] [BibTeXHide BibTeX]
@inproceedings{CompressedStack,
author={Barba, Luis and Korman, Matias and Langerman, Stefan and Sadakane, Kunihiko and Silveira, Rodrigo},
title={Space-Time Trade-offs for Stack-Based Algorithms},
booktitle={Proceedings of the 30th Symposium on Theoretical Aspects of Computer Science},
year={2013},
series={STACS'13},
pages={281-292},
month={February-March}
}
Circle separability queries in logarithmic time.
[AbstractHide Abstract]
G. Aloupis, , and S. Langerman.
In Proceedings of the 24th Canadian Conference on Computational Geometry, CCCG'12, pages 121–125, August 2012.
[pdf] [BibTeXHide BibTeX]
Abstract: In this paper we preprocess a set $P$ of $n$ points so that we can answer queries of the following form:Given a convex $m$-gon $Q$,report the minimum circle containing $P$ and excluding $Q$.Our data structure can be constructed in $O(n\log n)$ time using $O(n)$ space,and answers queries in $O(\log n + \log m)$ time.
In Proceedings of the 24th Canadian Conference on Computational Geometry, CCCG'12, pages 121–125, August 2012.
[pdf] [BibTeXHide BibTeX]
@inproceedings{NewCircleSeparability,
author={Aloupis, Greg and Barba, Luis and Langerman, Stefan},
title={Circle separability queries in logarithmic time},
booktitle={Proceedings of the 24th Canadian Conference on Computational Geometry},
year={2012},
series={CCCG'12},
pages={121-125},
month={August}
}
Disk constrained 1-center queries.
[AbstractHide Abstract]
.
In Proceedings of the 24th Canadian Conference on Computational Geometry, CCCG'12, pages 15–19, August 2012.
[pdf] [BibTeXHide BibTeX]
Abstract: We show that a set $P$ of $n$ points in the plane can be preprocessed in $O(n \log n)$-time to construct a data structure supporting $O(\log n)$-time queries of the following form: Find the minimum enclosing circle of $P$ with center on a given disk.
In Proceedings of the 24th Canadian Conference on Computational Geometry, CCCG'12, pages 15–19, August 2012.
[pdf] [BibTeXHide BibTeX]
@inproceedings{DiskConstrainedOneCenterQueries,
author={Barba, Luis},
title={Disk constrained 1-center queries},
booktitle={Proceedings of the 24th Canadian Conference on Computational Geometry},
year={2012},
series={CCCG'12},
pages={15-19},
month={August}
}
The Erdös-Sós conjecture for geometric graphs.
[AbstractHide Abstract]
, R. Fabila-Monroy, , , , , and .
In Proceedings of the European Workshop on Computational Geometry, EuroCG'12. March 2012.
[pdf] [arXiv] [BibTeXHide BibTeX]
Abstract: Let $f(n,k)$ be the minimum number of edges that must be removed from some complete geometric graph $G$ on $n$ points, so that there exists a tree on $k$ vertices that is no longer a planar subgraph of $G$. In this paper we show that $\left( \frac{1}{2} \right )\frac{n^2}{k-1}-\frac{n}{2}\le f(n,k) \le 2 \frac{n(n-2)}{k-2}$. For the case when $k=n$, we show that $2 \le f(n,n) \le 3$. For the case when $k=n$ and $G$ is a geometric graph on a set of points in convex position, we show that at least three edges must be removed.
In Proceedings of the European Workshop on Computational Geometry, EuroCG'12. March 2012.
[pdf] [arXiv] [BibTeXHide BibTeX]
@inproceedings{ErdosSosGeometricGraphs,
author={Barba, Luis and Fabila-Monroy, R and Lara, D. and Lea\~nos, Jes\'us and Rodr\'iguez, C. and Salazar, Gelasio. and Zaragoza, Francisco},
title={{T}he {E}rdös-{S}ós Conjecture for Geometric Graphs},
booktitle={Proceedings of the European Workshop on Computational Geometry},
year={2012},
series={EuroCG'12},
month={March}
}
Computing the visibility polygon using few variables.
[AbstractHide Abstract]
, M. Korman, S. Langerman, and R. Silveira.
In Proceedings of the 22nd International Symposium on Algorithms and Computation (ISAAC'11), pages 70–79. Yokohama, Japan, 2011.[pdf] [arXiv] [DOI] [BibTeXHide BibTeX]
Abstract: We present several algorithms for computing the visibility polygon of a simple polygon $\mathcal 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\overline{r})$ time, where $\overline{r}$ denotes the number of reflex vertices of $\mathcal P$ that are part of the output. The next two algorithms use $O(\log r)$ variables, and output the visibility polygon in $O(n\log r)$ randomized expected time or $O(n\log^2 r)$ deterministic time, where $r$ is the number of reflex vertices of $\mathcal P$.
In Proceedings of the 22nd International Symposium on Algorithms and Computation (ISAAC'11), pages 70–79. Yokohama, Japan, 2011.[pdf] [arXiv] [DOI] [BibTeXHide BibTeX]
@inproceedings{bkls-cvpufv-11,
author={Barba, Luis and Korman, Matias and Langerman, Stefan and Silveira, Rodrigo},
title={Computing the visibility polygon using few variables},
booktitle={Proceedings of the 22nd International Symposium on Algorithms and Computation (ISAAC'11)},
year={2011},
pages={70-79},
address={Yokohama, Japan}
}
On edge-disjoint empty triangles of point sets.
[AbstractHide Abstract]
, J. Cano, J. Urrutia, and .
In Proceedings of the XIV Spanish Meeting on Computational Geometry, EGC 2011, pages 15–18, July 2011.
[pdf] [BibTeXHide BibTeX]
Abstract: Let P be a set of points in the plane in general position. Any three points $x, y, x \in P$ determine a triangle $\Delta(x, y, z)$ of the plane. We say that $\Delta(x, y, z)$ is empty if its interior contains no element of $P$. In this paper we study the following problems: What is the size of the largest family of edge-disjoint triangles of a point set? How manytriangulations of $P$ are needed to cover all the empty triangles of $P$? We also study the following problem: What is the largest number of edge-disjoint triangles of $P$ containing a point $q$ of the plane in their interior? We establish upper and lower bounds for these problems.
In Proceedings of the XIV Spanish Meeting on Computational Geometry, EGC 2011, pages 15–18, July 2011.
[pdf] [BibTeXHide BibTeX]
@inproceedings{DisjointEdgeTriangles,
author={Barba, Luis and Cano, Javier and Urrutia, Jorge and Sakai, Toshimori},
title={On Edge-Disjoint Empty Triangles of Point Sets},
booktitle={Proceedings of the XIV Spanish Meeting on Computational Geometry},
year={2011},
series={EGC 2011},
pages={15-18},
month={July}
}
Dynamic circle separability between convex polygons.
[AbstractHide Abstract]
and J. Urrutia.
In Proceedings of the XIV Spanish Meeting on Computational Geometry, EGC 2011, pages 43–46, June 2011.
[pdf] [BibTeXHide BibTeX]
Abstract: Let $P$ be a convex polygon with $n$ vertices.In this paper we study a new variant of the circular separability problem in whichwe are allowed to preprocess the polygon $P$ into a data structure supporting queries of the following form:Given a convex polygon $Q$ as a list of its $m$ vertices,report the minimum circle containing $P$ and whose interior does not intersects $Q$.Our data structure can be constructed in linear time using $O(n)$ space,and answers queries in $O(\log n \log m)$ time.
In Proceedings of the XIV Spanish Meeting on Computational Geometry, EGC 2011, pages 43–46, June 2011.
[pdf] [BibTeXHide BibTeX]
@inproceedings{DynamicCircleSeparability,
author={Barba, Luis and Urrutia, Jorge},
title={Dynamic circle separability between convex polygons},
booktitle={Proceedings of the XIV Spanish Meeting on Computational Geometry},
year={2011},
series={EGC 2011},
pages={43-46},
month={June}
}
Subquadratic algorithms for algebraic generalizations of 3SUM.
[AbstractHide Abstract]
, , , S. Langerman, , and .
Discrete and Computational Geometry, 2018.
[arXiv] [BibTeXHide BibTeX]
Abstract: The 3SUM problem asks if an input $n$-set of real numbers contains a triple whose sum is zero. We consider the 3POL problem, a natural generalization of 3SUM where we replace the sum function by a constant-degree polynomial in three variables. The motivations are threefold. Raz, Sharir, and de Zeeuw gave an $O(n^{11/6})$ upper bound on the number of solutions of trivariate polynomial equations when the solutions are taken from the cartesian product of three $n$-sets of real numbers. We give algorithms for the corresponding problem of counting such solutions. Gr\o nlund and Pettie recently designed subquadratic algorithms for 3SUM. We generalize their results to 3POL. Finally, we shed light on the General Position Testing~(GPT) problem: ``Given $n$ points in the plane, do three of them lie on a line?'', a key problem in computational geometry.We prove that there exist bounded-degree algebraic decision trees of depth $O(n^{\frac{12}{7}+\varepsilon})$ that solve 3POL, and that 3POL can be solved in $O(n^2 {(\log \log n)}^\frac{3}{2} / {(\log n)}^\frac{1}{2})$ time in the real-RAM model. Among the possible applications of those results, we show how to solve GPT in subquadratic time when the input points lie on $o({(\log n)}^\frac{1}{6}/{(\log\log n)}^\frac{1}{2})$ constant-degree polynomial curves. This constitutes the first step towards closing the major open question of whether GPT can be solved in subquadratic time.To obtain these results, we generalize important tools --- such as batch range searching and dominance reporting --- to a polynomial setting. We expect these new tools to be useful in other applications.
Discrete and Computational Geometry, 2018.
[arXiv] [BibTeXHide BibTeX]
@article{3POLJournal,
author={Barba, Luis and Cardinal, Jean and Iacono, John and Langerman, Stefan and Ooms, Aur\'elien and Solomon, Noam},
title={{S}ubquadratic Algorithms for Algebraic Generalizations of 3{S}{U}{M}},
journal={Discrete and Computational Geometry},
year={2018}
}
Dynamic graph coloring.
[AbstractHide Abstract]
, , M. Korman, S. Langerman, A. van Renssen, , and S. Verdonschot.
Algorithmica, Jun 2018.
[DOI] [BibTeXHide BibTeX]
Abstract: In this paper we study the number of vertex recolorings that an algorithm needs to perform in order to maintain a proper coloring of a $c$-colorable graphunder insertion and deletion of vertices and edges.We assume that all updates keep the graph $c$-colorable and that $N$ is the maximum number of vertices in the graph at any point in time.We present two algorithms to maintain an approximation of the optimal coloring that, together, present a trade-off between the number of recolorings and the number of colors used:For any $d>0$, the first algorithm maintains a proper $O(c d N^{1/d})$-coloring and recolors at most $O(d)$ vertices per update.The second maintains an $O(c d)$-coloring using $O(dN^{1/d})$ recolorings per update. Both algorithms achieve the same asymptotic performance when $d = \log N$.Moreover, we show that for any algorithm that maintains a $c$-coloring of a $2$-colorable graph on $N$ vertices during a sequence of $m$ updates, there is a sequence of updates that forces the algorithm to recolor at least $\Omega(m\cdot N^\frac{2}{c(c-1)})$ vertices.
Algorithmica, Jun 2018.
[DOI] [BibTeXHide BibTeX]
@article{DynamicColoringJournal,
author={Barba, Luis and Cardinal, Jean and Korman, Matias and Langerman, Stefan and van Renssen, Andr\'e and Roeloffzen, Marcel and Verdonschot, Sander},
title={Dynamic Graph Coloring},
journal={Algorithmica},
year={2018},
month={Jun}
}
Continuous Yao graphs.
[AbstractHide Abstract]
, , P. Bose, J. de Carufel, , , , A. van Renssen, P. Taslakian, and S. Verdonschot.
Computational Geometry, Theory and Applications, 67(Supplement C):42 – 52, 2018.
[DOI] [BibTeXHide BibTeX]
Abstract: 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 < \theta \leq 2\pi$,we define the \emph{continuous Yao graph} $\cyao$ with vertex set $S$ and angle $\theta$ as follows. For each $p,q\in S$, we add an edge from $p$ to $q$ in $\cyao$if there exists a cone with apex $p$ and aperture $\theta$ such that $q$ is a closest pointto $p$ inside this cone.We study the spanning ratio of \cyao for different values of $\theta$.Using a new algebraic technique, we show that $\cyao$ is a spanner when $\theta \leq 2\pi /3$. We believe that this technique may be of independent interest. We also show that $\cyaopi$ is not a spanner, and that $\cyao$ may be disconnected for $\theta > \pi$, but on the other hand is always connected for $\theta\leq \pi$.Furthermore, we show that $\cyao$ is a region-fault-tolerant geometric spanner for convex fault regions when $\theta<\pi/3$. For half-plane faults, $\cyao$ remains connected if $\theta\leq\pi$.Finally, we show that $\cyao$ is not always self-approaching for any value of $\theta$.
Computational Geometry, Theory and Applications, 67(Supplement C):42 – 52, 2018.
[DOI] [BibTeXHide BibTeX]
@article{ContinuousYaoJournal,
author={Bakhshesh, Davood and Barba, Luis and Bose, Prosenjit and de Carufel, Jean-Lou and Damian, Mirela and Fagerberg, Rolf and Farshi, Mohammad and van Renssen, Andr\'e and Taslakian, Perouz and Verdonschot, Sander},
title={{C}ontinuous {Y}ao graphs},
journal={Computational Geometry, Theory and Applications},
year={2018},
volume={67},
number={Supplement C},
pages={42 - 52}
}
Linear transformation distance for bichromatic matchings.
[AbstractHide Abstract]
O. Aichholzer, , T. Hackl, , and B. Vogtenhuber.
Computational Geometry, Theory and Applications. Special Issue in Memoriam: Ferran Hurtado, 68:77–88, 2017.
[pdf] [arXiv] [DOI] [BibTeXHide BibTeX]
Abstract: 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.
Computational Geometry, Theory and Applications. Special Issue in Memoriam: Ferran Hurtado, 68:77–88, 2017.
[pdf] [arXiv] [DOI] [BibTeXHide BibTeX]
@article{BichromaticDistanceJournal,
author={Aichholzer, Oswin and Barba, Luis and Hackl, Thomas and Pilz, Alexander and Vogtenhuber, Birgit},
title={Linear transformation distance for bichromatic matchings},
journal={Computational Geometry, Theory and Applications. Special Issue in Memoriam: Ferran Hurtado},
year={2017},
volume={68},
pages={77-88}
}
Incremental Voronoi diagrams.
[AbstractHide Abstract]
, , , and S. Langerman.
Discrete and Computational Geometry, 58:822 – 848, 2017.
[DOI] [BibTeXHide BibTeX]
Abstract: We study the amortized number of combinatorial changes (edge insertions and removals) needed to update the graph structure of the Voronoi diagram $\VD(S)$ (and several variants thereof) of a set $S$ of $n$ sites in the plane as sites are added to the set.To that effect, we define a general update operation for planar graphs that can be used to model 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 to the Voronoi diagram is $O(\sqrt{n})$.A matching $\Omega(\sqrt{n})$ combinatorial lower bound is shown, even in the case where the graph representing the Voronoi diagram is a tree.This contrasts with the $O(\log{n})$ upper bound of Aronov et al.~(2006) for farthest-point Voronoi diagrams in the special case where the points are inserted in clockwise order along their convex hull.We then present a semi-dynamic data structure that maintains the Voronoi diagram of a set $S$ of $n$ sites in convex position.This data structure supports the insertion of a new site $p$ (and hence the addition of its Voronoi cell) 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 combinatorial result.The most distinctive feature of this data structure is that the graph of the Voronoi diagram is maintained explicitly at all times and can be retrieved and traversed in the natural way; this contrasts with other structures supporting nearest neighbor queries in that they do not maintain the Voronoi diagram after each insertion.This 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.
Discrete and Computational Geometry, 58:822 – 848, 2017.
[DOI] [BibTeXHide BibTeX]
@article{IncrementalVoronoiJournal,
author={Allen, Sarah and Barba, Luis and Iacono, John and Langerman, Stefan},
title={{I}ncremental {V}oronoi diagrams},
journal={Discrete and Computational Geometry},
year={2017},
volume={58},
pages={822 - 848}
}
Column planarity and partially-simultaneous geometric embedding.
[AbstractHide Abstract]
, , M. Hoffmann, V. Kusters, M. Saumell, and .
Journal of Graph Algorithms and Applications, 58-4:983–1002, 2017.
[DOI] [BibTeXHide BibTeX]
Abstract: We introduce the notion of column planarity of a subset $R$ of the vertices of a graph $G$.Informally, we say that $R$ is column planar in $G$ if we can assign $x$-coordinates to the vertices in $R$ such that any assignment of $y$-coordinates to them produces a partial embedding that can be completed to a plane straight-line drawing of $G$. Column planarity is both a relaxation and a strengthening of unlabeled level planarity. We prove near tight bounds for column planar subsets of trees: every tree on $n$ vertices contains a column planar set of size at least $14n/17$ and for any $\vaerepsilon > 0$ and any sufficiently large $n$, there exists an $n$-vertex tree in which every column planar subset has size at most $(5/6 + \varepsilon)n$. In addition, we show that every outerplanar graph has a column planar set of size at least $n/2$.We also consider a relaxation of simultaneous geometric embedding (SGE), which we call partially-simultaneous geometric embedding (PSGE). A PSGE of two graphs $G_1$ and $G_2$ allows some of their vertices to map to two different points in the plane. We show how to use column planar subsets to construct $k$-PSGEs in which $k$ vertices are still mapped to the same point. In particular, we show that every two trees on $n$ vertices admit an $11n/17$-PSGE and every two outerplanar graphs admit an $n/4$-PSGE.
Journal of Graph Algorithms and Applications, 58-4:983–1002, 2017.
[DOI] [BibTeXHide BibTeX]
@article{ColumnPlanarity,
author={Barba, Luis and Evans, William and Hoffmann, Michael and Kusters, Vincent and Saumell, Maria and Speckmann, Bettina},
title={Column planarity and partially-simultaneous geometric embedding},
journal={Journal of Graph Algorithms and Applications},
year={2017},
volume={58-4},
pages={983-1002}
}
Drawing the Horton set in an integer grid of minimum size.
[AbstractHide Abstract]
, , R. Fabila-Monroy, and .
Computational Geometry, Theory and Applications, 63:10–19, 2017.
[arXiv] [DOI] [BibTeXHide BibTeX]
Abstract: In 1978 Erd\"os asked if every sufficiently large set of points in general position in the plane contains the vertices of a convex $k$-gon, with the additional property that no other point of the set lies in its interior. Shortly after, Horton provided a construction---which is now called the Horton set---with no such $7$-gon. In this paper we show that the Horton set of n points can be realized with integer coordinates of absolute value at most $\frac{1}{2} n^{\frac{1}{2} \log(n/2)}$. We also show that any set of points with integer coordinates combinatorially equivalent (with the same order type) to the Horton set, contains a point with a coordinate of absolute value at least $c\cdot n^{\frac{1}{24}\log(n/2)}$, where c is a positive constant.
Computational Geometry, Theory and Applications, 63:10–19, 2017.
[arXiv] [DOI] [BibTeXHide BibTeX]
@article{HortonSetJournal,
author={Barba, Luis and Duque, Frank and Fabila-Monroy, R and Hidalgo-Toscano, Carlos},
title={{D}rawing the {H}orton set in an integer grid of minimum size},
journal={Computational Geometry, Theory and Applications},
year={2017},
volume={63},
pages={10-19}
}
A Linear-Time Algorithm for the Geodesic Center of a Simple Polygon.
[AbstractHide Abstract]
, , P. Bose, J. de Carufel, M. Korman, and .
Discrete and Computational Geometry, 56-4:836–859, 2015.
[pdf] [arXiv] [DOI] [BibTeXHide BibTeX]
Abstract: Let $P$ be a closed simple polygon with $n$ vertices.For any two points in $P$, the geodesic distance between them is the length of the shortest path that connects them among all paths contained in $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.In this paper we affirmatively answer this question and present a linear time algorithm to solve this problem.
Discrete and Computational Geometry, 56-4:836–859, 2015.
[pdf] [arXiv] [DOI] [BibTeXHide BibTeX]
@article{GeodesicCenterJournal,
author={Ahn, Hee-Kap and Barba, Luis and Bose, Prosenjit and de Carufel, Jean-Lou and Korman, Matias and Oh, Eunjin},
title={{A Linear-Time Algorithm for the Geodesic Center of a Simple Polygon}},
journal={Discrete and Computational Geometry},
year={2015},
volume={56-4},
pages={836-859}
}
Asymmetric polygons with maximum area.
[AbstractHide Abstract]
, , , R. Fabila-Monroy, and .
European Journal of Operational Research, 248(3):1123–1131, 2015.
[arXiv] [BibTeXHide BibTeX]
Abstract: We say that a polygon inscribed in the circle is asymmetric if it contains no two antipodal points being the endpoints of a diameter. Given $n$ diameters of a circle and a positive integer $k < n$, this paper addresses the problem of computing a maximum area asymmetric $k$-gon having as vertices $k < n$ endpoints of the given diameters. The study of this type of polygons is motivated by ethnomusiciological applications.
European Journal of Operational Research, 248(3):1123–1131, 2015.
[arXiv] [BibTeXHide BibTeX]
@article{AssymetricPolygonsJournal,
author={Barba, Luis and Caraballo, Luis Evaristo and Jose-Miguel, D\'iaz-B\'a\~nez and Fabila-Monroy, R and Perez, Edel},
title={Asymmetric polygons with maximum area},
journal={European Journal of Operational Research},
year={2015},
volume={248},
number={3},
pages={1123--1131}
}
Compatible connectivity-augmentation of planar disconnected graphs.
[AbstractHide Abstract]
G. Aloupis, , , , , and P. Morin.
Discrete and Computational Geometry, 54(2):459–480, 2015.
[pdf] [arXiv] [BibTeXHide BibTeX]
Abstract: Motivated by applications to graph morphing, we consider the following\emph{compatible connectivity-augmentation problem}: We are givena 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 thatthese vertices and edges can be added to $G_1,\ldots,G_k$ as points andstraight-line segments, respectively, to obtain $k$ planar straight-linedrawings isomorphic to the augmentation of $\mathcal G$. We showthat adding $\Theta(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 isachievable 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$.
Discrete and Computational Geometry, 54(2):459–480, 2015.
[pdf] [arXiv] [BibTeXHide BibTeX]
@article{CompatibleEmbeddingsJournal,
author={Aloupis, Greg and Barba, Luis and Carmi, Paz and Dujmovi\'c, Vida and Frati, Fabrizio and Morin, Pat},
title={Compatible Connectivity-Augmentation of Planar Disconnected Graphs},
journal={Discrete and Computational Geometry},
year={2015},
volume={54},
number={2},
pages={459--480}
}
Space-time trade-offs for stack-based algorithms.
[AbstractHide Abstract]
, M. Korman, S. Langerman, , and R. Silveira.
Algorithmica, 72(4):1097–1129, 2014.
[pdf] [arXiv] [BibTeXHide BibTeX]
Abstract: In memory-constrained algorithms the access to the input is restricted to be read-only, and the number of extra variables that the algorithm can use is bounded.In this paper we introduce the \emph{compressed stack technique}, a method that allows to transform algorithms whose main memory consumption takes the form of a stack into memory-constrained algorithms.Given an algorithm \alg\ that runs in $O(n)$ time using a stack of length $\Theta(n)$, we can modify it so that it runs in $O(n^2\log n/2^s)$ time using a workspace of $O(s)$ variables (for any $s\in o(\log n)$) or $O(n^{1+1/\log_p})$ time using $O(p\log_p n)$ 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, a 1-dimensional pyramid approximation of a 1-dimensional vector, and the visibility profile of a point inside a simple polygon.Our approach improves or matches up to a $O(\log n)$ factor the running time of the best-known results for these problems in constant-workspace models (when they exist), and gives a 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.
Algorithmica, 72(4):1097–1129, 2014.
[pdf] [arXiv] [BibTeXHide BibTeX]
@article{CompressedStackJournal,
author={Barba, Luis and Korman, Matias and Langerman, Stefan and Sadakane, Kunihiko and Silveira, Rodrigo},
title={Space-Time Trade-offs for Stack-Based Algorithms},
journal={Algorithmica},
year={2014},
volume={72},
number={4},
pages={1097--1129}
}
Theta-3 is connected.
[AbstractHide Abstract]
O. Aichholzer, , , P. Bose, M. Korman, A. van Renssen, P. Taslakian, and S. Verdonschot.
Computational Geometry, Theory and Applications, 47(9):910–917, 2014.
[pdf] [arXiv] [BibTeXHide BibTeX]
Abstract: In this paper, we show that the $\theta$-graph with three cones is connected.We also provide an alternative proof of the connectivity of the Yao-graph with three cones.
Computational Geometry, Theory and Applications, 47(9):910–917, 2014.
[pdf] [arXiv] [BibTeXHide BibTeX]
@article{Theta3Journal,
author={Aichholzer, Oswin and Bae, Sang Won and Barba, Luis and Bose, Prosenjit and Korman, Matias and van Renssen, Andr\'e and Taslakian, Perouz and Verdonschot, Sander},
title={Theta-3 is connected},
journal={Computational Geometry, Theory and Applications},
year={2014},
volume={47},
number={9},
pages={910-917}
}
Bichromatic compatible matchings.
[AbstractHide Abstract]
G. Aloupis, , S. Langerman, and D. Souvaine.
Computational Geometry, Theory and Applications, 48(8):622–633, 2014.
[pdf] [arXiv] [BibTeXHide BibTeX]
Abstract: For a set $R$ of $n$ red points and a set $B$ of$n$ blue points, a $BR$-matching is anon-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 , \ldots, 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 their paper ``Compatible matchings for bichromatic plane straight-line graphs''
Computational Geometry, Theory and Applications, 48(8):622–633, 2014.
[pdf] [arXiv] [BibTeXHide BibTeX]
@article{BichromaticMatchingsJournal,
author={Aloupis, Greg and Barba, Luis and Langerman, Stefan and Souvaine, Diane L.},
title={Bichromatic compatible matchings},
journal={Computational Geometry, Theory and Applications},
year={2014},
volume={48},
number={8},
pages={622--633}
}
Isoperimetric enclosures.
[AbstractHide Abstract]
G. Aloupis, , J. de Carufel, S. Langerman, and D. Souvaine.
Graph and Combinatorics, 31(2):361–392, 2015.
[pdf] [BibTeXHide BibTeX]
Abstract: Given a number $P$, we study the following three isoperimetric problems introduced by Besicovitch in 1952:(1) Let $S$ be a set of $n$ points in the plane. Among all the curves with perimeter $P$ that enclose $S$, what is the curve that encloses the maximum area?(2) Let $Q$ be a convex polygon with $n$ vertices. Among all the curves with perimeter $P$ contained in $Q$, what is the curve that encloses the maximum area?(3) Let $\circumR$ be a positive number. Among all the curves with perimeter $P$and circumradius $\circumR$,what is the curve that encloses the maximum area?In this paper, we provide a complete characterization for the solutions to Problems 1, 2 and 3.Moreover, we show that there are cases where the solution toProblem 1 cannot be computed exactly, however it is possible tocompute in $O(n \log n)$ time the exact combinatorial structure of thesolution, leaving only one real parameter, which can be approximatedwith arbitrary precision.To solve Problem 2, we provide an $O(n\log n)$ time algorithm to compute its solution exactly.In the case of Problem 3, we show that the problem can be solved in constant time.As a side note, we show that if $S$ is a set of $n$ points in the plane, then finding the curve of perimeter $P$ that encloses $S$ and has minimum area is NP-hard.
Graph and Combinatorics, 31(2):361–392, 2015.
[pdf] [BibTeXHide BibTeX]
@article{IsoperimetricEnclosuresJournal,
author={Aloupis, Greg and Barba, Luis and de Carufel, Jean-Lou and Langerman, Stefan and Souvaine, Diane L.},
title={Isoperimetric Enclosures},
journal={Graph and Combinatorics},
year={2015},
volume={31},
number={2},
pages={361-392}
}
The Erdös-Sós conjecture for geometric graphs.
[AbstractHide Abstract]
, R. Fabila-Monroy, , , , , and .
Discrete Mathematics and Theoretical Computer Science, 15(1):93–100, July 2012.
[arXiv] [BibTeXHide BibTeX]
Abstract: Let $f(n,k)$ be the minimum number of edges that must be removed from some complete geometric graph $G$ on $n$ points, so that there exists a tree on $k$ vertices that is no longer a planar subgraph of $G$. In this paper we show that $\left( \frac{1}{2} \right )\frac{n^2}{k-1}-\frac{n}{2}\le f(n,k) \le 2 \frac{n(n-2)}{k-2}$. For the case when $k=n$, we show that $2 \le f(n,n) \le 3$. For the case when $k=n$ and $G$ is a geometric graph on a set of points in convex position, we show that at least three edges must be removed.
Discrete Mathematics and Theoretical Computer Science, 15(1):93–100, July 2012.
[arXiv] [BibTeXHide BibTeX]
@article{ErdosSosJournal,
author={Barba, Luis and Fabila-Monroy, R and Lara, D. and Lea\~nos, Jes\'us and Rodr\'iguez, C. and Salazar, Gelasio. and Zaragoza, Francisco},
title={{T}he {E}rdös-{S}ós Conjecture for Geometric Graphs},
journal={Discrete Mathematics and Theoretical Computer Science},
year={2012},
volume={15},
number={1},
pages={93-100},
month={July}
}
Computing the visibility polygon using few variables.
[AbstractHide Abstract]
, M. Korman, S. Langerman, and R. Silveira.
Computational Geometry, Theory and Applications, pages 70–79, 2011.
[pdf] [arXiv] [BibTeXHide BibTeX]
Abstract: We present several algorithms for computing the visibility polygon of a simple polygon $\mathcal P$ of $n$ vertices (out of which $r$ are reflex) from a viewpoint inside $\mathcal P$, when $\mathcal P$ 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\overline{r})$ time, where $\overline{r}$ denotes the number of reflex vertices of $\mathcal P$ that are part of the output. Whenever we are allowed to use $O(s)$ variables, the running time decreases to $O(\frac{nr}{2^{s}}+n\log^2 r)$ (or $O(\frac{nr}{2^{s}}+n\log r)$ randomized expected time), where $s\in O(\log r)$. This is the first algorithm in which an exponential space-time trade-off for a geometric problem is obtained.
Computational Geometry, Theory and Applications, pages 70–79, 2011.
[pdf] [arXiv] [BibTeXHide BibTeX]
@article{visibilityJournal,
author={Barba, Luis and Korman, Matias and Langerman, Stefan and Silveira, Rodrigo},
title={Computing the visibility polygon using few variables},
journal={Computational Geometry, Theory and Applications},
year={2011},
pages={70-79}
}
On edge-disjoint empty triangles of point sets.
[AbstractHide Abstract]
, J. Cano, J. Urrutia, and .
In Pach, J., editor, Thirty Essays on Geometric Graph Theory, Algorithms and Combinatorics. Springer, 2012.
[pdf] [BibTeXHide BibTeX]
Abstract: Let P be a set of points in the plane in general position. Any three points $x, y, x \in P$ determine a triangle $\Delta(x, y, z)$ of the plane. We say that $\Delta(x, y, z)$ is empty if its interior contains no element of $P$. In this paper we study the following problems: What is the size of the largest family of edge-disjoint triangles of a point set? How manytriangulations of $P$ are needed to cover all the empty triangles of $P$? We also study the following problem: What is the largest number of edge-disjoint triangles of $P$ containing a point $q$ of the plane in their interior? We establish upper and lower bounds for these problems.
In Pach, J., editor, Thirty Essays on Geometric Graph Theory, Algorithms and Combinatorics. Springer, 2012.
[pdf] [BibTeXHide BibTeX]
@incollection{EssaysOnGeometricGraphTheory,
author={Barba, Luis and Cano, Javier and Urrutia, Jorge and Sakai, Toshimori},
title={On Edge-Disjoint Empty Triangles of Point Sets},
booktitle={Thirty Essays on Geometric Graph Theory},
publisher={Springer},
year={2012},
editor={Pach, J.},
series={Algorithms and Combinatorics}
}
On proximity problems in Euclidean spaces.
.
PhD thesis, Universite Libre de Bruxelles and Carelton University, 2016.
[BibTeXHide BibTeX]
.
PhD thesis, Universite Libre de Bruxelles and Carelton University, 2016.
[BibTeXHide BibTeX]
@mastersthesis{barbaPhD,
author={Barba, Luis},
title={{O}n proximity problems in {E}uclidean spaces},
school={Universite Libre de Bruxelles and Carelton University},
year={2016},
supervisor={Prosenjit Bose, Pat Morin, Stefan Langerman and Vida Dujmovic}
}
Problemas de proximidad sobre objetos geométricos en el plano (On proximity problems of geometric objects in the plane).
.
Master's thesis, Universidad Nacional Autónoma de México, 2011.
Supervisor: Jorge Urrutia.
[BibTeXHide BibTeX]
.
Master's thesis, Universidad Nacional Autónoma de México, 2011.
Supervisor: Jorge Urrutia.
[BibTeXHide BibTeX]
@mastersthesis{barbaMaster,
author={Barba, Luis},
title={{P}roblemas de proximidad sobre objetos geométricos en el plano ({O}n proximity problems of geometric objects in the plane)},
school={Universidad Nacional Autónoma de México},
year={2011},
supervisor={Jorge Urrutia},
type={Master}
}
Algoritmos de optimización sobre trayectorias monótonas en gráficas coloreadas por aristas (Optimization algorithms on montone paths in edge-colored graphs).
.
Bachelor's thesis, Universidad Nacional Autónoma de México, 2009.
Supervisor: Hortensia Galeana.
[BibTeXHide BibTeX]
.
Bachelor's thesis, Universidad Nacional Autónoma de México, 2009.
Supervisor: Hortensia Galeana.
[BibTeXHide BibTeX]
@mastersthesis{barbaBachelor,
author={Barba, Luis},
title={{A}lgoritmos de optimización sobre trayectorias monótonas en gráficas coloreadas por aristas ({O}ptimization algorithms on montone paths in edge-colored graphs)},
school={Universidad Nacional Autónoma de México},
year={2009},
supervisor={Hortensia Galeana},
type={Bachelor}
}