{"id":"arxiv/2602.22874","url":"https://arxiv.org/abs/2602.22874","tags":["cs.CG","cs.CC","cs.DM","cs.DS","math.CO"],"score":0,"title":"Flip Distance Between Triangulations of Convex Polygons is NP-Complete","domain":"cs.CG","source":"arxiv","authors":["Joseph Dorfer"],"reviews":0,"subject":"cs.CG","summary":"The complexity of determining the minimum number of flips that transform one triangulation of a convex polygon into another has been raised as an open problem by Culik and Wood [Inf. Proc. Letters 1982] and has been popularized through the study of extremal pairs of triangulations by Sleator, Tarjan, and Thurston [STOC 1986 & J. Am. Math. Society 1988]. The search for a hardness proof for the flip distance problem has yielded many (weaker) hardness-results in more general settings. Lubiw and Pathak [CCCG 2012, Comp. Geom. 2014] and Pilz [Comp. Geom. 2014] proved that computing the flip…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-02-26","reactions":{}}