# Victor Alvarez (Ph.D)

Saarland University
Information Systems Group
Building E 1.1, 3rd floor, room 3.09
Email: lastname@cs.uni-saarland.de
Telephone: +49 681 302 70144
Last update: May 2014

### In a nutshell

I was born in Mexico City, where I grew up and lived until the age of 25. I practiced rowing for about 9 years, of which about 5 were at international competitive level for Mexico's national team. During that time I started studying Physics at the Faculty of Sciences at UNAM, but later on I decided to change to Computer Science. My bachelor thesis was supervised by Prof. Dr. Jorge Urrutia. I obtained a master degree in Computer Science from Saarland University, in Saarbrücken, Germany, where my thesis was supervised by Prof. Dr. Raimund Seidel, who remained as my Ph.D supervisor. I am currently a Research Associate at the Information Systems Group headed by Prof. Dr. Jens Dittrich at Saarland University.

You might have landed here because of academic reasons, in that case, are you sure I'm the Victor Alvarez you're looking for? Otherwise you might be interested in horseback riding lessons, or even in a comic.

If you find on this website a broken link or elements that are not being properly rendered, I would greatly appreciate if you let me know. Thanks!

### Education

2007-2012:Ph.D in Computer Science (Dr.-Ing.) at Saarland University under supervision of Prof. Dr. Raimund Seidel. 2006-2007:Master in Computer Science (M. Sc.) at Saarland University and International Max-Planck Research School For Computer Science (IMPRS) under supervision of Prof. Dr. Raimund Seidel. 2001-2005:Bachelor of Computer Science (B. Sc.) at National Autonomous University of Mexico (UNAM) under supervision of Prof. Dr. Jorge Urrutia.

### Research interests

My current research is mainly focused on developing and engineering (new) algorithms and data structures for (1) indexing, and (2) tuple reconstruction; both for main-memory databases on multi-core systems. This development process ought to, for example, make the algorithms (or implementations) NUMA-aware when applicable — rather relevant nowadays, and to profile these in order to detect bottlenecks in performance scalability. Previously, nonetheless, I mostly worked in Combinatorial and Algorithmic Geometry, Algorithm Engineering, Combinatorics, Data Structures, and Parameterized Complexity. In general, I am highly interested in areas having algorithmic flavor.

### Publications

• Conferences: [C9]Victor Alvarez, Felix Martin Schuhknecht, Jens Dittrich, Stefan Richter. Main Memory Adaptive Indexing for Multi-core Systems. In Proc. of the 10th International Workshop on Data Management on New Hardware (DaMoN '14), Snowbird, USA, 2014.
[C8]Victor Alvarez, Karl Bringmann, Saurabh Ray, Raimund Seidel. Counting Triangulations Approximately. In Proc. of the 25th Canadian Conference on Computational Geometry (CCCG '13), Waterloo, Canada, 2013.
Abstract: We consider the problem of counting straight-edge triangulations of a given set $P$ of $n$ points in the plane. Until very recently it was not known whether the exact number of triangulations of $P$ can be computed asymptotically faster than by enumerating all triangulations. We now know that the number of triangulations of $P$ can be computed in $O^{*}(2^{n})$ time, which is less than the lower bound of $\Omega(2.43^{n})$ on the number of triangulations of any point set. In this paper we address the question of whether one can approximately count triangulations in sub-exponential time. We present an algorithm with sub-exponential running time and sub-exponential approximation ratio, that is, if we denote by~$\Lambda$ the output of our algorithm, and by $c^{n}$ the exact number of triangulations of $P$, for some positive constant $c$, we prove that $c^{n}\leq\Lambda\leq c^{n}\cdot 2^{o(n)}$. This is the first algorithm that in sub-exponential time computes a $(1+o(1))$-approximation of the base of the number of triangulations, more precisely, $c\leq\Lambda^{\frac{1}{n}}\leq(1 + o(1))c$. Our algorithm can be adapted to approximately count other crossing-free structures on~$P$, keeping the quality of approximation and running time intact. Our algorithm may be useful in guessing, through experiments, the right constants $c_1$ and $c_2$ such that the number of triangulations of any set of $n$ points is between $c_1^n$ and $c_2^n$. Currently there is a large gap between $c_1$ and $c_2$. We know that $c_1 \geq 2.43$ and $c_2 \leq 30$.
[C7]Victor Alvarez, Erin W. Chambers, László Kozma. Privacy by Fake Data: A Geometric Approach. In Proc. of the 25th Canadian Conference on Computational Geometry (CCCG '13), Waterloo, Canada, 2013.
Abstract: We study the following algorithmic problem: given $n$ points within a finite $d$-dimensional box, what is the smallest number of extra points that need to be added to ensure that every $d$-dimensional unit box is either empty, or contains at least $k$ points. We motivate the problem through an application to data privacy, namely $k$-anonymity. We show that minimizing the number of extra points to be added is strongly NP-complete, but admits a Polynomial Time Approximation Scheme (PTAS). In some sense, this is the best we can hope for, since a Fully Polynomial Time Approximation Scheme (FPTAS) is not possible, unless P=NP.
[C6]Victor Alvarez, Raimund Seidel. A Simple Aggregative Algorithm for Counting Triangulations of Planar Point Sets and Related Problems. In Proc. of the 29th Symposium on Computational Geometry (SoCG '13), pages 1-8, Rio de Janeiro, Brazil, 2013. DOI=10.1145/2462356.2462392.
Abstract: We give an algorithm that determines the number $\mbox{tr}(S)$ of straight line triangulations of a set $S$ of $n$ points in the plane in worst case time $O(n^2 2^n)$. This is the the first algorithm that is provably faster than enumeration, since $\mbox{tr}(S)$ is known to be $\Omega(2.43^n)$ for any set $S$ of $n$ points. Our algorithm requires exponential space. The algorithm generalizes to counting all triangulations of $S$ that are constrained to contain a given set of edges. It can also be used to compute an optimal triangulation of $S$ (unconstrained or constrained) for a reasonably wide class of optimality criteria (that includes e.g. minimum weight triangulations). Finally, the approach can also be used for the random generation of triangulations of $S$ according to the perfect uniform distribution. The algorithm has been implement and is substantially faster than existing methods on a variety of inputs.
[C5]Victor Alvarez, Karl Bringmann, Radu Curticapean, Saurabh Ray. Counting Crossing-free Structures. In Proc. of the 28th Symposium on Computational Geometry (SoCG '12), pages 61-68, Chapel Hill, USA, 2012. DOI=10.1145/2261250.2261259.
Abstract: Let $P$ be a set of $n$ points in the plane. A crossing-free structure on $P$ is a straight-edge planar graph with vertex set in $P$. Examples of crossing-free structures include triangulations of $P$, and spanning cycles of $P$, also known as polygonalizations of $P$, among others. There has been a large amount of research trying to bound the number of such structures. In particular, bounding the number of triangulations spanned by $P$ has received considerable attention. It is currently known that every set of $n$ points has at most $O(30^{n})$ and at least $\Omega(2.43^{n})$ triangulations. However, much less is known about the algorithmic problem of counting crossing-free structures of a given set $P$. For example, no algorithm for counting triangulations is known that, on all instances, performs faster than enumerating all triangulations. In this paper we develop a general technique for computing the number of crossing-free structures of an input set $P$. We apply the technique to obtain algorithms for computing the number of triangulations and spanning cycles of $P$. The running time of our algorithms is upper bounded by $n^{O(k)}$, where $k$ is the number of onion layers of $P$. In particular, we show that our algorithm for counting triangulations is not slower than $O(3.1414^{n})$. Given that there are several well-studied configurations of points with at least $\Omega(3.464^{n})$ triangulations, and some even with $\Omega(8^{n})$ triangulations, our algorithm is the first to asymptotically outperform any enumeration algorithm for such instances. In fact, it is widely believed that any set of $n$ points must have at least $\Omega(3.464^{n})$ triangulations. If this is true, then our algorithm is strictly sub-linear in the number of triangulations counted. We also show that our techniques are general enough to solve the restricted triangulation counting problem, which we prove to be $W[2]$-hard in the parameter $k$. This implies a "no free lunch" result: In order to be fixed-parameter tractable, our general algorithm must rely on additional properties that are specific to the considered class of structures.
[C4]Victor Alvarez, Atsuhiro Nakamoto. Colored Quadrangulations with Steiner Points. Selected papers of The Thailand-Japan Joint Conference on Computational Geometry and Graphs (TJJCCGG ’12), LNCS 8296, pages 20-29, Bangkok, Thailand, 2013. DOI=10.1007/978-3-642-45281-9_2. Preliminary version in Proc. of the 28th European Workshop on Computational Geometry (EuroCG '12), pages 249-252, Assisi, Italy, 2012.
Abstract: Let $P\subset\mathbb{R}^{2}$ be a $k$-colored set of $n$ points in general position, where $k\geq 2$. A $k$-colored quadrangulation of $P$ is a properly colored straight-edge plane graph $G$ with vertex set $P$ such that the boundary of the unbounded face of $G$ coincides with the convex hull of $P$ and that each bounded face of $G$ is quadrilateral. It is easy to check that in general not every $k$-colored $P$ admits a $k$-colored quadrangulation, and hence the use of extra points, for which we can choose the color among the $k$ available colors, is required in order to obtain one. These extra points are known in the literature as Steiner points. In this paper, we show that if $P$ satisfies some condition for the colors of the points in the convex hull, then a $k$-colored quadrangulation of $P$ can always be constructed using less than $\frac{(16 k-2) n+7 k-2}{39 k-6}$ Steiner points. Our upper bound improves the previous known upper bound for $k=3$, and represents the first bounds for $k\geq 4$.
[C3]Victor Alvarez, David G. Kirkpatrick, Raimund Seidel. 2011. Can nearest neighbor searching be simple and always fast?. In Proc. of the 19th European conference on Algorithms (ESA '11), pages 82-92, Saarbrücken, Germany, 2011. DOI=10.1007/978-3-642-23719-5_8.
Abstract: Nearest Neighbor Searching, i.e. determining from a set $S$ of $n$ sites in the plane the one that is closest to a given query point $q$, is a classical problem in computational geometry. Fast theoretical solutions are known, e.g. point location in the Voronoi Diagram of $S$, or specialized structures such as so-called Delaunay hierarchies. However, practitioners tend to deem these solutions as too complicated or computationally too costly to be actually useful. Recently in ALENEX 2010 Birn et al. proposed a simple and practical randomized solution. They reported encouraging experimental results and presented a partial performance analysis. They argued that in many cases their method achieves logarithmic expected query time but they also noted that in some cases linear expected query time is incurred. They raised the question whether some variant of their approach can achieve logarithmic expected query time in all cases. The approach of Birn et al. derives its simplicity mostly from the fact that it applies only one simple type of geometric predicate: which one of two sites in $S$ is closer to the query point $q$. In this paper we show that any method for planar nearest neighbor searching that relies just on this one type of geometric predicate can be forced to make at least $n-1$ such predicate evaluations during a worst case query.
[C2]Victor Alvarez. Even Triangulation of Planar Set of Points with Steiner Points. In Proc. of the 26th European Workshop on Computational Geometry (EuroCG '10), pages 119-122, Dortmund, Germany, 2010.
Abstract: Let $P\subset\mathbb{R}^{2}$ be a set of $n$ points of which $k$ are interior points. Let us call a triangulation $T$ of $P$ even if all its vertices have even degree, and pseudo-even if at least the $k$ interior vertices have even degree. (Pseudo-)Even triangulations have one nice property; their vertices can be $3$-colored, see here for example. Since one can easily check that for some sets of points, such triangulation do not exist, we show an algorithm that constructs a set $S$ of at most $\left\lfloor\frac{k + 2}{3}\right\rfloor$ Steiner points (extra points) along with a pseudo-even triangulation $T$ of $P\cup S = V(T)$.
[C1]Victor Alvarez, Raimund Seidel. Approximating the Minimum Spanning Tree of Set of Points in the Hausdorff Metric. In Proc. of the 24th European Workshop on Computational Geometry (EuroCG '08), pages 119-122, Nancy, France, 2008.
Abstract: We study the problem of approximating $\mbox{MST}(P)$, the Euclidean minimum spanning tree of a set $P$ of $n$ points in $[0,1]^d$, by a spanning tree of some subset $Q\subset P$. We show that if the weight of $(P)$ is to be approximated, then in general $Q$ must be large. If the shape of $\mbox{MST}(P)$ is to be approximated, then this is always possible with a small $Q$. More specifically, for any $0<\varepsilon<1$ we prove:
1. There are sets $P\subset [0, 1]^{d}$ of arbitrarily large size $n$ with the property that any subset $Q'\subset P$ that admits a spanning tree $T'$ with $\bigl| \left|T'\right|-\left|\mbox{MST}(P)\right|\bigr| < \varepsilon\cdot\left|\mbox{MST}(P)\right|$ must have size at least $\Omega\left({n}^{1 - 1/d}\right)$. Here $|T|$ denotes the weight, i.e. the sum of the edge lengths of tree $T$.
2. For any $P\subset [0,1]^d$ of size $n$ there exists a subset $Q\subseteq P$ of size $O\left(1/\varepsilon^{d}\right)$ that admits a spanning tree $T$ that is $\varepsilon$-close to $\mbox{MST}(P)$ in terms of Hausdorff distance (which measures shape dissimilarity).
3. This set $Q$ and this spanning tree $T$ can be computed in time $O\left(\tau_d(n) + 1/\varepsilon^d\log\left(1/\varepsilon^d\right)\right)$ for any fixed dimension $d$. Here $\tau_d(n)$ denotes the time necessary to compute the minimum spanning tree of $n$ points in $\mathbb{R}^d$, which is known to be $O(n\log n)$ for $d=2$, $O\left((n\log n)^{4/3}\right)$ for $d=3$, and $O\left(n^{2-2/\left(\lceil d/2\rceil+1\right)+\phi}\right)$, with $\phi>0$ arbitrarily small, for $d>3$, see here.
All the results hold not only for the Euclidean metric $L_2$ but also for any $L_{p}$ metric with $1\leq p\leq\infty$ as underlying metric.
• Journals: [J4]Victor Alvarez, Karl Bringmann, Saurabh Ray, Raimund Seidel. Counting Triangulations and other Crossing-Free Structures Approximately. Computational Geometry, Theory and Applications. To appear 2014. Special Issue on the 25th Canadian Conference on Computational Geometry (CCCG '13).
Abstract:We consider the problem of counting straight-edge triangulations of a given set~$P$ of $n$ points in the plane. Until very recently it was not known whether the exact number of triangulations of $P$ can be computed asymptotically faster than by enumerating all triangulations. We now know that the number of triangulations of $P$ can be computed in $O^{*}(2^{n})$ time, see here, which is less than the lower bound of $\Omega(2.43^{n})$ on the number of triangulations of any point set. In this paper we address the question of whether one can approximately count triangulations in sub-exponential time. We present an algorithm with sub-exponential running time and sub-exponential approximation ratio, that is, denoting by $\Lambda$ the output of our algorithm and by $c^{n}$ the exact number of triangulations of $P$, for some positive constant $c$, we prove that $c^{n}\leq\Lambda\leq c^{n}\cdot 2^{o(n)}$. This is the first algorithm that in sub-exponential time computes a $(1+o(1))$-approximation of the base of the number of triangulations, more precisely, $c\leq\Lambda^{\frac{1}{n}}\leq(1 + o(1))c$. Our algorithm can be adapted to approximately count other crossing-free structures on $P$, keeping the quality of approximation and running time intact. In this paper we show how to do this for matchings and spanning trees.
[J3]Victor Alvarez. Parity-constrained Triangulations using Steiner points. Graphs and Combinatorics. December 2013. DOI=10.1007/s00373-013-1389-6.
Abstract: Let $P\subset\mathbb{R}^{2}$ be a set of $n$ points, of which $k$ lie in the interior of the convex hull $\text{CH}(P)$ of $P$. Let us call a triangulation $T$ of $P$ even (odd) if and only if all its vertices have even (odd) degree, and pseudo-even (pseudo-odd) if at least the $k$ interior vertices have even (odd) degree. On the one hand, triangulations having all its interior vertices of even degree have one nice property; their vertices can be 3-colored, see here for example. On the other hand, odd triangulations have recently found an application in the colored version of the classic "Happy Ending Problem" of Erdős and Szekeres, see here.
In this paper we show that there are sets of points that admit neither pseudo-even nor pseudo-odd triangulations. Nevertheless, we show how to construct a set of Steiner points $S = S(P)$ of size at most $\frac{k}{3} + c$, where $c$ is a positive constant, such that a pseudo-even (pseudo-odd) triangulation can be constructed on $P\cup S$. Moreover, we also show that even (odd) triangulations can always be constructed using at most $\frac{n}{3} + c$ Steiner points, where again $c$ is a positive constant. Our constructions have the property that every Steiner point lies in the interior of $\text{CH}(P)$.
[J2]Victor Alvarez, Raimund Seidel. Approximating the minimum weight spanning tree of a set of points in the Hausdorff metric. Computational Geometry, Theory and Applications 43:2, pages 94-98. February 2010. Special Issue on the 24th European Workshop on Computational Geometry (EuroCG '08). DOI=10.1016/j.comgeo.2009.04.005.
Abstract: We study the problem of approximating $\mbox{MST}(P)$, the Euclidean minimum spanning tree of a set $P$ of $n$ points in $[0,1]^d$, by a spanning tree of some subset $Q\subset P$. We show that if the weight of $(P)$ is to be approximated, then in general $Q$ must be large. If the shape of $\mbox{MST}(P)$ is to be approximated, then this is always possible with a small $Q$. More specifically, for any $0<\varepsilon<1$ we prove:
1. There are sets $P\subset [0, 1]^{d}$ of arbitrarily large size $n$ with the property that any subset $Q'\subset P$ that admits a spanning tree $T'$ with $\bigl| \left|T'\right|-\left|\mbox{MST}(P)\right|\bigr| < \varepsilon\cdot\left|\mbox{MST}(P)\right|$ must have size at least $\Omega\left({n}^{1 - 1/d}\right)$. Here $\left|T\right|$ denotes the weight, i.e. the sum of the edge lengths of tree $T$.
2. For any $P\subset [0,1]^d$ of size $n$ there exists a subset $Q\subseteq P$ of size $O\left(1/\varepsilon^{d}\right)$ that admits a spanning tree $T$ that is $\varepsilon$-close to $\mbox{MST}(P)$ in terms of Hausdorff distance (which measures shape dissimilarity).
3. This set $Q$ and this spanning tree $T$ can be computed in time $O\left(\tau_{d,p}(n) + 1/\varepsilon^d\log\left(1/\varepsilon^d\right)\right)$ for any fixed dimension $d$. Here $\tau_{d,p}(n)$ denotes the time necessary to compute the minimum weight spanning tree of $n$ points in $\mathbb{R}^d$ under any fixed metric $L_p,\ 1\leq p\leq\infty$, where $\tau_{2,p}(n) = O(n\log n)$, see here, $\tau_{3,2}(n) = O\left((n\log n)^{4/3}\right)$, and $\tau_{d, 2}(n) = O\left(n^{2-2/\left(\lceil d/2\rceil+1\right)+\phi}\right)$, with $\phi>0$ arbitrarily small, for $d>3$, see here. Also $\tau_{3,1}(n)$ and $\tau_{3,\infty}(n)$ is known to be $O(n\log n)$, see here.
[J1]Victor Alvarez, Toshinori Sakai, Jorge Urrutia. Bichromatic Quadrangulations with Steiner Points. Graphs and Combinatorics 23:1, pages 85-98. February 2007. DOI=10.1007/s00373-007-0715-2.
Abstract: Let $P$ be a $k$-colored point set in general position, $k\geq 2$. A family of quadrilaterals with disjoint interiors $Q_{1},\ldots, Q_{m}$ is called a quadrangulation of $P$ if $V(Q_{1})\cup\cdots V(Q_{m}) = P$, the edges of all $Q_{i}$ join points with different colors, and $Q_{1}\cup\cdots\cup Q_{m} = Conv(P)$. In general it is easy to see that not all $k$-colored point sets admit a quadrangulation; when they do, we call them quadrangulatable. For a point set to be quadrangulatable it must satisfy that its convex hull $Conv(P)$ has an even number of points and that consecutive vertices of $Conv(P)$ receive different colors. This will be assumed from now on. In this paper, we study the following type of questions: Let $P$ be a $k$-colored point set. How many Steiner points in the interior of $Conv(P)$ do we need to add to $P$ to make it quadrangulatable? When $k$ = 2, we usually call $P$ a bichromatic point set, and its color classes are usually denoted by $R$ and $B$, i.e. the red and blue elements of $P$. In this paper, we prove that any bichromatic point set $P = R\cup B$ where $|R| = |B| = n$ can be made quadrangulatable by adding at most $\left\lfloor\frac{n - 1}{3}\right\rfloor + \left\lfloor\frac{n}{2}\right\rfloor + 1$ Steiner points, and that $\frac{m}{3}$ Steiner points are occasionally necessary. To prove the latter, we also show that the convex hull of any monochromatic point set $P$ of $n$ elements can be always partitioned into a set $S = \{S_{1}, \ldots, S_{t}\}$ of star-shaped polygons with disjoint interiors, where $V(S_{1})\cup\cdots V(S_{t}) = P$, and $t\leq\left\lfloor\frac{n−1}{3}\right\rfloor + 1$. For $n = 3k$ this bound is tight. Finally, we prove that there are 3-colored point sets that cannot be completed to 3-quadrangulatable point sets.
• Other manuscripts: [M4]Victor Alvarez, Felix Martin Schuhknecht, Jens Dittrich, Stefan Richter. Main Memory Adaptive Indexing for Multi-core Systems. Computing Research Repository (CoRR), 2014. abs/1404.2034. This is the extended version of [C9].
[M3]Victor Alvarez, Karl Bringmann, Saurabh Ray, Raimund Seidel. Counting Triangulations and other Crossing-free Structures Approximately. Computing Research Repository (CoRR), 2013. abs/1404.0261. This is the extended version of [C8] and the unpolished version of [J4].
Abstract: We consider the problem of counting straight-edge triangulations of a given set $P$ of $n$ points in the plane. Until very recently it was not known whether the exact number of triangulations of $P$ can be computed asymptotically faster than by enumerating all triangulations. We now know that the number of triangulations of $P$ can be computed in $O^{*}(2^{n})$ time AS13, which is less than the lower bound of $\Omega(2.43^{n})$ on the number of triangulations of any point set SSW11. In this paper we address the question of whether one can approximately count triangulations in sub-exponential time. We present an algorithm with sub-exponential running time and sub-exponential approximation ratio, that is, denoting by $\Lambda$ the output of our algorithm, and by $c^{n}$ the exact number of triangulations of $P$, for some positive constant $c$, we prove that $c^{n}\leq\Lambda\leq c^{n}\cdot 2^{o(n)}$. This is the first algorithm that in sub-exponential time computes a $(1+o(1))$-approximation of the base of the number of triangulations, more precisely, $c\leq\Lambda^{\frac{1}{n}}\leq(1 + o(1))c$. Our algorithm can be adapted to approximately count other crossing-free structures on $P$, keeping the quality of approximation and running time intact. In this paper we show how to do this for matchings and spanning trees.
[M2]Victor Alvarez, Karl Bringmann, Radu Curticapean, Saurabh Ray. Counting Triangulations and other Crossing-free Structures via Onion Layers. Computing Research Repository (CoRR), 2013. abs/1312.4628. This is the extended version of [C5] and it is currently under review at a journal.
Abstract: Let $P$ be a set of $n$ points in the plane. A crossing-free structure on $P$ is a straight-edge planar graph with vertex set in $P$. Examples of crossing-free structures include triangulations of $P$, and spanning cycles of $P$, also known as polygonalizations of $P$, among others. There has been a large amount of research trying to bound the number of such structures. In particular, bounding the number of triangulations spanned by $P$ has received considerable attention. It is currently known that every set of $n$ points has at most $O(30^{n})$ and at least $\Omega(2.43^{n})$ triangulations. However, much less is known about the algorithmic problem of counting crossing-free structures of a given set $P$. For example, no algorithm for counting triangulations is known that, on all instances, performs faster than enumerating all triangulations.
In this paper we develop a general technique for computing the number of crossing-free structures of an input set $P$. We apply the technique to obtain algorithms for computing the number of triangulations and spanning cycles of $P$. The running time of our algorithms is upper bounded by $n^{O(k)}$, where $k$ is the number of onion layers of $P$. In particular, we show that our algorithm for counting triangulations is not slower than $O(3.1414^{n})$. Given that there are several well-studied configurations of points with at least $\Omega(3.464^{n})$ triangulations, and some even with $\Omega(8^{n})$ triangulations, our algorithm is the first to asymptotically outperform any enumeration algorithm for such instances. In fact, it is widely believed that any set of $n$ points must have at least $\Omega(3.464^{n})$ triangulations. If this is true, then our algorithm is strictly sub-linear in the number of triangulations counted. We show experiments comparing our algorithm for counting triangulations with the algorithm presented here, which is supposed to be very fast in practice.
We also show that our techniques are general enough to solve the restricted triangulation counting problem, which we prove to be $W[2]$-hard in the parameter $k$. This implies a "no free lunch" result: In order to be fixed-parameter tractable, our general algorithm must rely on additional properties that are specific to the considered class of structures.
[M1]Victor Alvarez, Karl Bringmann, Saurabh Ray. A Simple Sweep Line Algorithm for Counting Triangulations and Pseudo-triangulations. Computing Research Repository (CoRR), 2013. abs/1312.3188. Currently under review at a journal.
Abstract: Let $P\subset\mathbb{R}^{2}$ be a set of $n$ points. In A99 and ARSS03 an algorithm for counting triangulations and pseudo-triangulations of $P$, respectively, is shown. Both algorithms are based on the divide-and-conquer paradigm, and both work by finding sub-structures on triangulations and pseudo-triangulations that allow the problems to be split. These sub-structures are called triangulation paths for triangulations, or T-paths for short, and zig-zag paths for pseudo-triangulations, or PT-paths for short. Those two algorithms have turned out to be very difficult to analyze, to the point that no good analysis of their running time has been presented so far. The interesting thing about those algorithms, besides their simplicity, is that they experimentally indicate that counting can be done significantly faster than enumeration.
In this paper we show two new algorithms, one to compute the number of triangulations of $P$, and one to compute the number of pseudo-triangulations of $P$. They are also based on T-paths and PT-paths respectively, but use the sweep line paradigm and not divide-and-conquer. The important thing about our algorithms is that they admit a good analysis of their running times. We will show that our algorithms run in time $O^{*}(t(P))$ and $O^{*}(pt(P))$ respectively, where $t(P)$ and $pt(P)$ is the largest number of T-paths and PT-paths, respectively, that the algorithms encounter during their execution. Moreover, we show that $t(P) = O^{*}(9^{n})$, which is the first non-trivial bound on $t(P)$ to be known.
While the algorithm for counting triangulations of ABCR12 is faster in the worst case, $O^{*}\left(3.1414^{n}\right)$, than our algorithm, $O^{*}\left(9^{n}\right)$, there are sets of points where the number of T-paths is $O(2^{n})$. In such cases our algorithm may be faster. Furthermore, it is not clear whether the algorithm presented in ABCR12 can be modified to count pseudo-triangulations so that its running time remains $O^{*}(c^n)$ for some small constant $c\in\mathbb{R}$. Therefore, for counting pseudo-triangulations (and possibly other similar structures) our approach seems better.

### Awards

• Best paper award at the 29th Symposium on Computational Geometry (SoCG '13), Rio de Janeiro, Brazil.

### The rest of the time

Some random pictures of mine from Flickr:

I'm an active user of Last.fm. Here are some statistics of my listening habits: