Advertisement
Published in:
2005 | OriginalPaper | Chapter
Minimum Weight Triangulation by Cutting Out Triangles
Authors : Magdalene Grantson, Christian Borgelt, Christos Levcopoulos
Published in: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We describe a fixed parameter algorithm for computing the minimum weight triangulation (MWT) of a simple polygon with (
n
–
k
) vertices on the perimeter and
k
hole vertices in the interior, that is, for a total of
n
vertices. Our algorithm is based on cutting out empty triangles (that is, triangles not containing any holes) from the polygon and processing the parts or the rest of the polygon recursively. We show that with our algorithm a minimum weight triangulation can be found in time at most
O
(
n
3
k
!
k
), and thus in
O
(
n
3
) if
k
is constant. We also note that
k
! can actually be replaced by
b
k
for some constant
b
. We implemented our algorithm in Java and report experiments backing our analysis.