Flip Distance Between Triangulations of a Simple Polygon is NP-Complete.

Oswin Aichholzer Wolfgang Mulzer Alexander Pilz

Published in: Discret. Comput. Geom. (2015)

Keyphrases

np complete
simple polygon
randomly generated
computational complexity
satisfiability problem
convex hull
np hard
endpoints
x ray
polynomial time complexity