Bounds on Optimally Triangulating Connected Subsets of the Minimum Weight Convex Partition
Magdalene Grantson, Christos Levcopoulos · 2005
Given a set S of n points, we show that the length of 1) the minimum weight triangulation (MWT)ofthe minimum weight convex partition (MWCP)ofS (TMWCP) is at most Θ(n) longer than the MWT of S if collinearity of two or more edges is allowed and Θ(log n) otherwise, 2) the MWT of the minimum spanning tree (MST) of the MWCP of S (T mst(MWCP)) isatmostΘ(n) longer than the MWT of S if collinearity of two or more edges is allowed and Θ(log n) otherwise, 3) the MWT of any connected subset G of the MWCP of S (T MWCP(G)) isatmostΘ(n) longer than the MWT of S if collinearity of two or more edges is allowed. 1