A Linear-Time Approximation Scheme for Minimum, Weight Triangulation of Convex Polygons.

Christos Levcopoulos Drago Krznaric

Published in: Algorithmica (1998)

Keyphrases

minimum weight
convex hull
minkowski sum
bipartite graph
greedy heuristic
spanning tree
randomized algorithm
weighted graph
simple polygon
digital convexity
minimum spanning tree
endpoints
maximum cardinality
approximation algorithms
minimum length