Publications |
● Computational/combinatorial/discrete
geometry ○ General ○ The flip corner |
● For nonspecialists |
For a 2009 survey on
the topic see
Flips
in planar graphs. Prosenjit Bose, Ferran
Hurtado.
Computational Geometry: Theory and Applications,Vol. 42, Issue
1, January 2009, Pages 60-80.
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)