Planar Minimum-Weight Triangulations
Jesper Jansson
November, 1995
Master's Thesis in Computer Science
Abstract
The classic problem of finding a minimum-weight triangulation
for a given planar straight-line graph is considered in this paper.
A brief overview of known methods is given in addition to some new results.
A parallel greedy triangulation algorithm is presented along with
experimental data that suggest a logarithmic relationship between
the number of input vertices and its running time in the average case.
Next, some new graph-based algorithms for parallel dynamic programming for
simple polygons are described and analyzed.
They are combined into a general algorithm that can be
employed when the number of available processors is anywhere between
O(n2 / log(n)) and O(n6 / log(n))
to reach running times that vary from
O(n log(n)) to O(log(n)2), where
n denotes the number of vertices that the polygons contain.
As a side effect, a method for constructing the greedy triangulation
of simple polygons
with O(n4.75 / log(n)2) processors
in O(n0.75 log(n)) time
is obtained.
Finally, an 
(n) lower bound for the nonoptimality of
the MST-triangulation heuristic
and an (n0.5) lower bound for the
nonoptimality of the GST-triangulation heuristic are proved.
PostScript version (756501 bytes).
A printed version of the thesis can be obtained from:
Technical Reports Librarian
Department of Computer Science
Lund University
Box 118
SE-221 00 Lund
Sweden
E-mail:
Anne-Marie.Westerberg@cs.lth.se
Back