Javascript verkar inte påslaget? - Vissa delar av Lunds universitets webbplats fungerar inte optimalt utan javascript, kontrollera din webbläsares inställningar.
Du är här

Minimum weight triangulation by cutting out triangles

Publiceringsår: 2005
Språk: Engelska
Sidor: 984-994
Publikation/Tidskrift/Serie: Algorithms and computation / Lecture notes in computer science
Volym: 3827
Dokumenttyp: Konferensbidrag
Förlag: Springer


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.


  • Computer Science


16th International Symposium, ISAAC 2005
  • VR 2002-4049
  • ISSN: 1611-3349
  • ISSN: 0302-9743
  • ISBN: 978-3-540-30935-2

Box 117, 221 00 LUND
Telefon 046-222 00 00 (växel)
Telefax 046-222 47 20
lu [at] lu [dot] se

Fakturaadress: Box 188, 221 00 LUND
Organisationsnummer: 202100-3211
Om webbplatsen