DIAMONDS ARE NOT A MINIMUM WEIGHT TRIANGULATION'S BEST FRIEND

Prosenjit Bose1 Luc Devroye2

Department of Computer Science School of Computer Science
University of British Columbia McGill University
Vancouver, Canada V6T 1Z4 Montreal, Canada H3A 2A7

and
William Evans3

Department of Computer Science
University of British Columbia
Vancouver, Canada V6T 1Z4

Abstract. Two recent methods have increased hopes of finding a polynomial time solution to the problem of computing the minimum weight triangulation of a set S of n points in the plane. Both involve computing what was believed to be a connected or nearly connected subgraph of the minimum weight triangulation, and then completing the triangulation optimally. The first method uses the light graph of S as its initial subgraph. The second method uses the lmt-skeleton of S. Both methods rely, for their polynomial time bound, on the initial subgraphs having only a constant number of components. Experiments performed by the authors of these methods seemed to confirm that randomly chosen point sets displayed this desired property. We show that there exist point sets where the number of components is linear in n. In fact, the expected number of components in either graph on a randomly chosen point set is linear in n, and the probability of the number of components exceeding some constant times n tends to one.

Keywords and phrases. Light edges, locally minimal triangulations, minimum weight triangulations, probabilistic analysis, computational geometry.

CR Categories: 3.74, 5.25, 5.5.

1 Supported by a Killam and an NSERC post-doctoral fellowship. 2 Supported by NSERC Grant A4456 and by FCAR Grant 90-ER-0291. 3 Supported by an NSERC Canada International Fellowship.