We consider the problems of finding two optimal triangulations
of a convex polygon: MaxMin area and MinMax area. These are the
triangulations that maximize the area of the smallest area triangle in a triangulation,
and respectively minimize the area of the largest area triangle
in a triangulation, over all possible triangulations. The problem was originally
solved by Klincsek by dynamic programming in cubic time [2]. Later,
Keil and Vassilev devised an algorithm that runs in O(n^2 log n) time...
ACM Computing Classification System (1998): G.2.2, F.2.2.
Recently, Markov, Vassilev and Manev [2] proposed an algorithm for finding the longest path in 2-trees. In this paper, we describe an implementation of the algorithm. We briefly discuss the algorithm and present example that helps the reader grasp the main algorithmic ideas. Further, we discuss the important stages in the implementation of the algorithm and justify the decisions taken. Then, we present experimental results and...
* A preliminary version of this paper was presented at XI Encuentros de Geometr´ia
Computacional, Santander, Spain, June 2005.
We consider sets of points in the two-dimensional Euclidean
plane. For a planar point set in general position, i.e. no three points collinear,
a triangulation is a maximal set of non-intersecting straight line segments
with vertices in the given points. These segments, called edges, subdivide the
convex hull of the set into triangular regions called faces or...
Download Results (CSV)