Flip Distance Between Triangulations of Convex Polygons is NP-Complete
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2602.22874
curl -X POST /api/v1/records/arxiv/2602.22874/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2602.22874/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'