My publications as of 17 February 2016. Also available as plain text.

Dynamic graph coloring.
[AbstractHide Abstract]

, , M. Korman, S. Langerman, A. van Renssen, , and S. Verdonschot.

Submitted to the 43rd International Colloquium on Automata, Languages and Programming.

[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.

Submitted to the 43rd International Colloquium on Automata, Languages and Programming.

[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 43rd International Colloquium on Automata, Languages and Programming}, year={2016} }

A lower bound for deterministic asynchronous rendez-vous on the line.
[AbstractHide Abstract]

, P. Bose, J. de Carufel, S. Langerman, and .

Submitted to the 35th ACM Symposium on Principles of Distributed Computing.

[pdf] [BibTeXHide BibTeX]

Abstract: Two agents located at distance $D$ from each other on an infinite line want to meet. This problem is known as the \emph{rendez-vous problem}. In this paper, we study a version where the movements of the agents are not synchronized. To guarantee that the two agents can meet, we need to break symmetry. To do so, we assign two different \emph{labels} (binary strings) to the agents. We denote the length of a binary string $L$ by $|L|$. The goal is to design an algorithm which,given any label as an input, produces a sequence of moves, a \emph{strategy}. Every pair of strategies produced by the algorithm must enable the two agents following them to meet in a finite amount of time. The \emph{cost} of an algorithm is equal to the total distance the agents have to travel before they meet, in the worst case. Denote by $|L_{\min}|$ and $|L_{\max}|$ the two labels assigned to the agents, where $|L_{\min}| \leq |L_{\max}|$. When $D$ is given to the agents, the best known algorithm has a cost of $\sim |L_{\min}|^2 D$. We write $f \sim g$ whenever $\lim_{x\rightarrow \infty} f(x)/g(x) = 1$. When $|L_{\min}| = |L_{\max}| = \ell$ is given to the agents, but $D$ is not given to them, the best known algorithm has a cost of $\sim e^2\ell^2 D$, where $e \approx 2.71828$ is the Euler's number. When nothing is given to the agents, the best known algorithm has a cost of $O(D\log^2(D) + |L_{\max}|D\log(D)+|L_{\min}|^2D+|L_{\min}||L_{\max}|\log(|L_{\min}|))$. We establish the first non-trivial lower bound on the cost of any deterministic algorithm that solves any of these three variants. We prove that asymptotically, any algorithm has a cost of at least $0.07302 \, |L_{\min}|^2\, D$. Our lower bound argument relies on a new technique which uses the asymptotic formula for the number of strongly unimodal sequences.

Submitted to the 35th ACM Symposium on Principles of Distributed Computing.

[pdf] [BibTeXHide BibTeX]

@inproceedings{AsynchronousRendezVous, author={Barba, Luis and Bose, Prosenjit and de Carufel, Jean-Lou and Langerman, Stefan and Por, Atila}, title={A Lower Bound for Deterministic Asynchronous Rendez-Vous on the Line}, booktitle={Proceedings of the 35th ACM Symposium on Principles of Distributed Computing}, year={2016} }

A Linear-Time Algorithm for the Geodesic Center of a Simple Polygon.
[AbstractHide Abstract]

, , P. Bose, J. de Carufel, M. Korman, and .

Submitted to Discrete and Computational Geometry.

[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.

Submitted to Discrete and Computational Geometry.

[pdf] [arXiv] [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} }

Linear transformation distance for bichromatic matchings.
[AbstractHide Abstract]

O. Aichholzer, , T. Hackl, , and B. Vogtenhuber.

Submitted to Computational Geometry, Theory and Applications. Special Issue in Memoriam: Ferran Hurtado.

[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.

Submitted to Computational Geometry, Theory and Applications. Special Issue in Memoriam: Ferran Hurtado.

[pdf] [arXiv] [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={2015} }

Asymmetric polygons with maximum area.
[AbstractHide Abstract]

, , , R. Fabila-Monroy, and .

Accepted in European Journal of Operational Research.

[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.

Accepted in European Journal of Operational Research.

[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} }

Compatible connectivity-augmentation of planar disconnected graphs.
[AbstractHide Abstract]

G. Aloupis, , , , , and P. Morin.

Accepted in Discrete and Computational Geometry.

[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$.

Accepted in Discrete and Computational Geometry.

[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} }

Space-time trade-offs for stack-based algorithms.
[AbstractHide Abstract]

, M. Korman, S. Langerman, , and R. Silveira.

Published in Algorithmica.

[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.

Published in Algorithmica.

[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} }

Theta-3 is connected.
[AbstractHide Abstract]

O. Aichholzer, , , P. Bose, M. Korman, A. van Renssen, P. Taslakian, and S. Verdonschot.

Published in Computational Geometry, Theory and Applications.

[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.

Published in Computational Geometry, Theory and Applications.

[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.

Published in Computational Geometry, Theory and Applications.

[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''

Published in Computational Geometry, Theory and Applications.

[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} }

Isoperimetric enclosures.
[AbstractHide Abstract]

G. Aloupis, , J. de Carufel, S. Langerman, and D. Souvaine.

Published in Graph and Combinatorics.

[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.

Published in Graph and Combinatorics.

[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 .

Published in Discrete Mathematics and Theoretical Computer Science.

[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.

Published in Discrete Mathematics and Theoretical Computer Science.

[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.

Published in Computational Geometry, Theory and Applications.

[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.

Published in Computational Geometry, Theory and Applications.

[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} }

The farthest-point geodesic voronoi diagram of points on the boundary of a simple polygon.
[AbstractHide Abstract]

, , and .

Accepted in the 32st Symposium on Computational Geometry.

[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.

Accepted in the 32st Symposium on Computational Geometry.

[pdf] [BibTeXHide BibTeX]

@inproceedings{GeodesicVoronoi, author={Ahn, Hee-Kap and Barba, Luis and Oh, Eunjin}, title={The farthest-point geodesic Voronoi 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.

Accepted in the 32st Symposium on Computational Geometry.

[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.

Accepted in the 32st Symposium on Computational Geometry.

[BibTeXHide BibTeX]

@inproceedings{IncrementalVoronoi, author={Allen, Sarah and Barba, Luis and Iacono, John and Langerman, Stefan}, title={Incremental Voronoi 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]

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.
, , 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]

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]

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$.
G. Aloupis, , , , , and P. Morin.

In Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms, pages 1602–1615, 2015.

[pdf] [arXiv] [BibTeXHide BibTeX]

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={Drawing the Horton 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]

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.
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]

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]

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.
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]

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={On the stretch factor of the Theta-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]

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.
, R. Fabila-Monroy, , , , , and .

In Proceedings of the European Workshop on Computational Geometry, EuroCG'12. March 2012.

[pdf] [arXiv] [BibTeXHide BibTeX]

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} }

Top-down skiplists.
[AbstractHide Abstract]

and P. Morin.

Available in ArXiv.

[pdf] [arXiv] [BibTeXHide BibTeX]

Abstract: In this paper we develop a dictionary data structure, supporting insert and delete operations in $O(\log n)$ amortized time, while being able to search for an element $x$ in $O(\log w(x))$ amortized time. Here, $w(x)$ denotes the size of the working set of $x$, i.e., the number of elements that have been accessed in the structure since the last time $x$ was accessed. Moreover, the number of comparisons performed for this search is $(1+\delta)\log w(x) + O(1)$, where $\delta>0$ is an arbitrarily small constant.We present a lower bound in the comparison model showing that any comparison-based dictionary always contains an element $x$ such that at least $\log w(x) + \log\log w(x) - O(1)$ comparisons are required to search for $x$.

Available in ArXiv.

[pdf] [arXiv] [BibTeXHide BibTeX]

@article{2014arXiv1407.7917B, author={Barba, Luis and Morin, Pat}, title={Top-Down Skiplists}, journal={ArXiv}, year={2014} }

On edge-disjoint empty triangles of point sets.
[AbstractHide Abstract]

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.
, J. Cano, J. Urrutia, and .

In Pach, J., editor, Thirty Essays on Geometric Graph Theory, Algorithms and Combinatorics. Springer, 2012.

[pdf] [BibTeXHide BibTeX]

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} }

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} }