Geometric bistellarflips:the tting,the context
and a construction
Francisco Santos∗
Abstract.We give a lf-contained introduction to the theory of condary polytopes and geometric bistellarflips in triangulations of polytopes and point ts,as well as a review of some of the known results and connections to algebraic geometry,topological combinatorics, and other areas.
As a new result,we announce the construction of a point t in general position with a disconnected space of triangulations.This shows,for thefirst time,that the pot of strict polyhedral subdivisions of a point t is not always connected.
Mathematics Subject Classification(2000).Primary52B11;Secondary52B20.
Keywords.Triangulation,point configuration,bistellarflip,polyhedral subdivision,discon-nectedflip-graph.
大雪纷纷何所似
Introduction
Geometric bistellarflips are“elementary moves”,that is,minimal changes,between triangulations of a point t in affine space R d.In their prent form they were in-troduced around1990by Gel’fand,Kapranov and Zelevinskii during their study of discriminants and resultants for spar polynomials[28],[29].Not surprisingly,then, the bistellarflips have veral connections to algebraic geometry.For example, the author’s previous constructions of point ts with a disconnected graph of trian-gulations in dimensionsfive and six[64],[67]imply that certain algebraic schemes considered in the literature[4],[13],[33],[57],including the so-called toric Hilbert scheme,are sometimes not connected.
Triangulations of point ts play also an obvious role in applied areas such as com-putational geometry or computer aided geometric design,where a region of the plane or3-space is triangulated in order to approximate a surface,answer proximity or vis-ibility questions,etc.See,for example,the survey articles[8],[10],or[25].In the fields,flips between triangulations have also been considered since long[40].Among other things,they are ud as the basic step to compute an optimal triangulation of a point t incrementally,that is,adding the points one by one.This incrementalflip-ping algorithm is the one usually preferred for,for example,computing the Delaunay ∗Partially supported by the Spanish Ministry of Education and Science,grant number MTM2005-08618-C02-02.
Proceedings of the International Congress
of Mathematicians,Madrid,Spain,2006
©2006European Mathematical Society
少年闰土笔记932Francisco Santos triangulation,as“the most intuitive and easy to implement”[8],and yet as efficient as any other.
In both the applied and the theoretical framework,the situation is the same:a fixed t of points A⊂R d is given to us(the“sites”for a Delaunay triangulation computation,the test points for a surface reconstruction,or a t of monomials, reprented as points in Z d,in the algebro-geometric context)and we need to either explore the collection of all possible triangulations of this t A or arch for a particular one that satisfies certain optimality properties.Geometric bistellarflips are the natural way to do this.For this reason,it was considered one of the main open questions in polytope theory ten years ago whether point ts exist with triangulations that cannot be connected via theflips[80].As we have mentioned above,this question was answered positively by the author of this paper,starting in dimension five.The question is still open in dimensions three and four.
This paper intends to be an introduction to this topic,organized in three parts.
Thefirst ction is a lf-contained introduction to the theory of geometric bistellar flips and condary polytopes in triangulations of point ts,aimed at the non-expert. The results in it are certainly not new(most come from the original work of Gel’fand, Kapranov and Zelevinskii mentioned above)but the author wants to think that this ction has some expository novelty;veral examples that illustrate the theory are given,and our introduction of geometric bistellarflipsfirst as certain polyhedral sub-divisions and only afterwards as transformations between triangulations is designed to show that the definition is as natural as can be.This ctionfinishes with an account of the state-of-the-art regarding knowledge of the graph offlips for ts with“few”points or“small”dimension,with an emphasis on the differences between dimensions two and three.
The cond ction develops in more detail the two contexts in which we have mentioned thatflips are interesting(computational geometry and algebraic geome-try)together with other two,that we call“combinatorial topology”and“topological combinatorics”.Combinatorial topology refers to the study of topological manifolds via triangulations of them.Bistellarflips have been propod as a tool for manifold recognition[18],[46],and triangulations of the3-sphere without bistellarflips other than“inrtion of new vertices”are known[24].Topological combinatorics refers to topological methods in combinatorics,particularly to the topology of partially or-dered ts(pots)via their order complexe
s.The graph of triangulations of a point t A consists of thefirst two levels in the pot of polyhedral subdivisions of A, which in turn is just an instance of veral similar pots studied in combinatorics with motivations and applications ranging from oriented matroid theory to bundle theories in differential geometry.
The third ction announces for thefirst time the construction of a point t in general position who graph of triangulations is not connected.The details of the proof appear in[68].The point t is also the smallest one known so far to have a disconnected graph offlips.
Geometric bistellar flips:the tting,the context and a construction 933Theorem.There is a t of 17points in general position in R 6who graph of triangulations is not connected.
安曼集团As usual in geometric combinatorics,a finite point t A ⊂R d is said to be in general position if no d +2of the points lie in an affine hyperplane.Equivalently,if none of the |A |d +1 determinants defined by the point t vanish.Point ts in general position form an open den subt in the space R n ×d of ts of dimension d with n elements.That is to say,“random point ts”are in general position.Point ts that are not in general position are said to be in special position .
The connectivity question has received special attention in general position even before disconnecte
d examples in special position were found.For example,Chal-lenge 3in [80]and Problem 28in [50]specifically ask whether disconnected graphs of flips exist for point ts in special position (the latter asks this only for dimen-sion 3).Although it was clear (at least to the author of this paper)from the previous examples of disconnected graphs of flips that examples in general position should also exist,modifying tho particular examples to general position and proving that their flip-graphs are still not connected is not an easy task for quite intrinsic reasons:the proofs of non-connectednes in [64],[67]are bad on the fact that the point ts considered there are cartesian products of lower dimensional ones.
In our opinion,an example of a disconnected graph of flips in general position is interesting for the following three reasons:
1.The definition of flip that is most common in computational geometry coin-cides with ours (which is the standard one in algebraic geometry and polytope combinatorics)only for point ts in general position.In special position,the computational geometric definition is far more restrictive and,in particular,taking it makes disconnected graphs of flips in special position be “no sur-pri”.For example,Edelsbrunner [25]says that the flip-graph among the (three)triangulations of a regular octahedron is not connected;e Section
2.1.
2.Leaving aside the question of definition,in engineering applications the co-ordinates of points are usually approximate and there is no loss in perturbing them into general position.That is,the general position ca is sometimes the only ca.
3.Even in a purely theoretical framework,point ts in general position have somehow simpler properties than tho in special position.If a point t A in special position has a non-connected graph of flips then automatically some subt of A (perhaps A itlf)has a disconnected pot of subdivisions.This pot is sometimes called the Baues pot of A and its study is (part of)the so-called generalized Baues problem.See Section 2.3,or [61]for more preci information on this.In particular,the prent example is the first one (proven)to have a disconnected Baues pot.
Corollary.There is a t of at most 17points in R 6who pot of proper polyhedral subdivisions is not connected.
934Francisco Santos梁迎春
1.The tting
1.1.Triangulations.Regular triangulations and subdivisions
Triangulations and polyhedral subdivisions.A (convex)polytope P is the convex hull of a finite t of points in the affine space R d .A face of P is its interction with any hyperplane that does not cross the relative interior of P .(Here,the relative interior of S ⊆R d is the interior of S regarded as a subt of its affine span).We remind the reader that the faces of dimensions 0,1,d −2and d −1of a d -polytope are called vertices,edges,ridges and facets,respectively.Vertices of P form the minimal S such that P =conv (S).右边喉咙痛
A k -simplex is a polytope who vertices (necessarily k +1)are affinely indepen-dent.It has k +1i +1 faces of each dimension i =0,...,k ,which are all simplices.Definition 1.1.Let A be a finite point t in R d .A triangulation of A is any collec-tion T of affinely spanning and affinely independent subts of A with the following properties:
1.if σand σ are in T ,then conv (σ)∩conv (σ )is a face of both conv (σ)and conv (σ ).That is,T induces a geometric simplicial complex in R k ;
2. σ∈T conv (σ)=conv (A ).That is,T covers the convex hull of A .
Note that our definition allows for some points of A not to be ud at all in a particular triangulation.Extremal points (vertices of conv (A ))are ud in every triangulation.The elements of a triangulation T are called cells .
We can define polyhedral subdivisions of A by removing the requirement of the ts σto be affinely independent in Definition 1.1.Since a general subt σof A may contain points which are not vertices of conv (σ),now the fact that the elements of a subdivision are subts of A rather than “subpolytopes”is not just a formality:points which are not vertices of any “cell”in the subdivision may still be considered “ud”as elements of some cells.In order to get a nicer concept of polyhedral subdivision,we also modify part 1in Definition 1.1,adding the following (redundant for affinely independent ts)condition:
conv (σ∩σ )∩σ=conv (σ∩σ )∩σ for all σ,σ ∈T.
That is,if A contains some point in the common face conv (σ∩σ )of conv (σ)and conv (σ )but not a vertex of it,that point is either in both or in none of σand σ .Polyhedral subdivisions of A form a partially ordered t (or pot )with respect to the following refinement relation:
S refines S :⇔for all σ ∈S there exists σ∈S such that σ⊆σ .
归州
Triangulations are,of cour,the minimal elements in this pot.The pot has a unique maximal element,namely the trivial suvdivision {A }.
Geometric bistellarflips:the tting,the context and a construction935 Example1.2.Let A be the following t offive points a1,...,a5in the plane.We take the convention that points are displayed as columns in a matrix,and that an extra homogenization coordinate(the row of1’s in the following matrix)is added so that linear algebra,rather than affine geometry,can be ud for computations:
A=⎛
⎜⎝
a1a2a3a4a5
03031
00331
11111
⎞
⎟⎠(1)
The following are the nine polyhedral subdivisions of A.Arrows reprent the refine-ment relation,pointing from the coarr to thefiner subdivision.For clarity,we write “125”meaning{a1,a2,a5},and so on.Figure1shows pictures of the subdivisions.In the corners are the four triangulations of A and in the middle is the trivial subdivision.
{125,135,235,234}←{1235,234}→{135,234}
↑↑↑
{125,135,2345}←{12345}→{1234}
↓↓↓
{125,135,245,345}←{1245,1345}→{124,134}
The last two columns of subdivisions geometrically induce the same decomposition
Figure1.The nine polyhedral subdivisions of a certain point t.
of conv(A)into subpolygons.Still,we consider them different subdivisions since the middle column“us”the interior point5while the right column does not.
936Francisco Santos Regular subdivisions.Let a point t A be given,and choo a function w:A→R to lift A to R d+1as the point t通眉
A w:={(a,w(a):a∈A}.
A lower facet of conv(A w)is a facet who supporting hyperplane lies below the inte-rior of conv(A w).The following is a polyhedral subdivision of A,whereπ:R d+1→R d is the projection that forgets the last coordinate:
T w:={π(F∩A w):F is a lower facet of conv(A w)}. Geometrically,we are projecting down onto A the lower envelope of A w,keeping track of points that lie in the lower boundary even if they are not vertices of a facet. Definition1.3.The polyhedral subdivisions and triangulations that can be obtained in this way are called regular.
649年If w is sufficiently generic then T w is clearly a triangulation.Regular triangulations are particularly simple and yet quite versatile.They appear in different contexts under different names such as coherent[29],convex[36],[77],Gale[49],or generalized (or,weighted)Delaunay[25]triangulations.The latter refers to the fact that the Delaunay triangulation of A,probably the most ud triangulation in applications, is the regular triangulation obtained with w(a)= a 2,where · is the euclidean norm.
Example1.4.Let
A=⎛
⎝
a1a2a3a4a5a6
400211
040121
004112
⎞
⎠.
This is a configuration of six points in the affine plane with equation x1+x2+x3=4 in R3.Since the matrix is already homogeneous(meaning precily that columns lie in an affine hyperplane)we do not need the extra homogenization row.The configuration consists of two parallel equilateral triangles,one inside the other.We leave it to the reader to check that the following are two non-regular triangulations(e Figure2):
T1:={124,235,136,245,356,146,456},
T2:={125,236,134,145,256,346,456}.
This example is the smallest possible,since1-dimensional point configurations and point configurations with at most d+3points in any dimension d only have regular triangulations.The former is easy to prove and the latter wasfirst shown in[44].The earliest appearance of the two non-regular triangulations that we know of is in[20], although they are cloly related to Schönhardt’s classical example of a non-convex 3-polytope that cannot be triangulated[69].1
1We describe Schönhardt’s polyhedron and its relation to this example in Example1.21.
