Computational/combinatorial/discrete geometry: The flip corner

A flip is a local transformation in which a new object in a class is produced by means of a small modification of a previous object in the same class. It is common to define a graph having a node for each object in the class, adjacencies corresponding to flips. Then connectedness, diameter, shortest paths, and so on, are suitable expressions for natural issues about the flip operation.

Graph of triangulations of a convex polygon and tree of triangulations. Ferran Hurtado and Marc Noy.
Computational Geometry: Theory and Applications 13(1999) 179-188.
Define a graph G_T(n) with one node for each triangulation of a convex n-gon. Place an edge between each pair of nodes that differ by a single flip: two triangles forming a quadrilateral are exchanged for the other pair of triangles forming the same quadrilateral. In this paper we introduce a tree of all triangulations of polygons with any number of vertices which gives a unified framework in which several results on G_T(n) admit new and simple proofs.

Flipping edges in triangulations. Ferran Hurtado, Marc Noy and Jorge Urrutia.
Discrete and Computational Geometry 22:333-346 (1999)
In this paper we study the problem of flipping edges in triangulations of polygons and point sets. One of the main results is that any triangulation of a set of n points in general position contains at least $\lceil (n-4)/2 \rceil$ edges that can be flipped. We also prove that O(n + k^2) flips are sufficient to transform any triangulation of an n -gon with k reflex vertices into any other triangulation. We produce examples of n -gons with triangulations T and T' such that to transform T into T' requires $\Omega$(n2) flips. Finally we show that if a set of n points has k convex layers, then any triangulation of the point set can be transformed into any other triangulation using at most O(kn) flips.

Simultaneous edge flipping in triangulations. Jerôme Galtier, Ferran Hurtado, Marc Noy, Stephane Perennes and Jorge Urrutia.
To appear in Intenational Journal of Computational Geometry and Applications.
We generalize the operation of flipping an edge in a triangulation to that of flipping several edges simultaneously or in parallel. We obtain several results, mainly sharp bounds on the number of parallel flips that are needed to transform a triangulation into another. Our results hold for triangulations of point sets and for polygons.
Click here to get a zipped version (1664K).

Geometric tree graphs of points in convex position. Carmen Hernando, Ferran Hurtado, Alberto Márquez, Mercè Mora and Marc Noy.
Discrete Applied Mathematics 93 (1999) 51-66.
Given a set $P$ of points in the plane, the geometric tree graph of $P$ is defined as the graph $T(P)$ whose vertices are non-crossing rectilinear spanning trees of $P$, and where two trees $T_1$ and $T_2$ are adjacent if $T_2 = T_1 -e+f$ for some edges $e$ and $f$. In this paper we concentrate on the geometric tree graph of a set of $n$ points in convex position, denoted by $G_n$. We prove several results about $G_n$, among them the existence of Hamilton cycles and the fact that they have maximum connectivity.

Graphs of non-crossing perfect matchings. Carmen Hernando, Ferran Hurtado and Marc Noy.
Graphs and Combinatorics Vol. 18, N. 3, pp. 517-532, 2002.
Ext. abstract in Proc. 15th European Conference on Computational Geometry, pp- 97-100, 1999.
Let P be a set of n=2m points in convex position, and let M be the graph having vertices corresponding to non-crossing perfect matchings in P, two of them Q and R being joined by and edge when R=Q-(a,b)-(c,d)+(a,d)+(a,c) for some points a,b,c,d in P. We prove that M has diameter m-1, is bipartite, has no Hamilton path for m odd, m>3, and is Hamiltonian for m even, m>2.
Click here to get a postscript version (430K).

On Local Transformation of Polygons with Visibility Properties . Carmen Hernando, Ferran Hurtado and Michael Houle.
Theoretical Computer Science, Vol. 289, n. 2, pp. 919-937, 2002.
Extended abstract in Lecture Notes in Computer Science 1858 (Proc. 6th International Computing and Combinatorics Conference (COCOON'00), Sydney), Springer-Verlag, 2000, pp. 54-63.
For general simple polygons on fixed point sets, it is still not known whether the class of polygons on the set is connected via a constant-size local transformation. In this paper, we exhibit a simple local transformation for which the classes of (weakly) edge-visible and (weakly) externally visible polygons are connected. The latter class is particularly interesting as it is the most general polygon class known to be connected under local transformation.
Click here to get a postscript version (383K).

On flips in polyhedral surfaces. Oswin Aichholzer, Lyuba Alboul and Ferran Hurtado.
International Journal of Foundations of Computer Science, Vol. 13 No. 2, pp. 303-311, 2002.
Ext. abstract in Proc. 17th European Conference on Computational Geometry, pp- 27-30, 2001.
Let $V$ be a finite point set in 3D-space, and let ${\cal S}(V)$ be the set of triangulated polyhedral surfaces homeomorphic to a sphere with vertex set $V$. Let $abc$ and $cbd$ be two adjacent triangles belonging to a surface $S\in {\cal S}(V)$; the {\sl flip} of the edge $bc$ would replace these two triangles by the triangles $abd$ and $adc$. The flip operation is only considered when it does not produce a self intersecting surface. In this paper we show that given two surfaces $S_1, S_2\in {\cal S}(V)$, it is possible that there is no sequence of flips transforming $S_1$ into $S_2$, even in the case that $V$ consists of points in convex position.
Click here to get a gzipped postscript version (69K).

Sequences of spanning trees and a fixed tree theorem. Oswin Aichholzer, Franz Aurenhammer and Ferran Hurtado.
Computational Geometry: Theory and Applications 21(2002) 3-20.
Sequences of spanning trees and a fixed tree theorem. Let ${\cal T}_S$ be the set of all crossing-free spanning trees of a planar $n$-point set $S$. We prove that ${\cal T}_S$ contains, for each of its members $T$, a length-decreasing sequence of trees $T_o,\ldots,T_k$ such that $T_o=T$, $T_k=MST(S)$, $T_i$ does not cross $T_{i-1}$ for $i=1,\ldots,k$, and $k=O(\log n)$. Here $MST(S)$ denotes the Euclidean minimum spanning tree of the point set $S$. As an implication, the number of length-improving and planar edge moves needed to transform a tree $T \in {\cal T}_S$ into $MST(S)$ is only $O(n\log n)$. Moreover, it is possible to transform any two trees in ${\cal T}_S$ into each other by means of a local and constant-size edge slide operation. Applications of these results to morphing of simple polygons are possible by using a crossing-free spanning tree as a skeleton description of a polygon.

(Last update of this page:January 2002)