Bounds on optimally triangulating connected subsets of the minimum weight convex partition.

Magdalene Grantson Christos Levcopoulos

Published in: EuroCG (2005)

Keyphrases

minimum weight
randomized algorithm
bipartite graph
spanning tree
greedy heuristic
weighted graph
lower bound
upper bound
connected components
maximum cardinality
minimum spanning tree
average case
convex hull
greedy algorithm
vc dimension
worst case
dynamic programming