The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

Minimum weight triangulation by cutting out triangles

På svenska

Author

Summary, in English

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.

Department/s

  • Computer Science

Publishing year

2005

Language

English

Pages

984-994

Publication/Series

Algorithms and computation / Lecture notes in computer science

Volume

3827

Document type

Conference paper

Publisher

Springer

Topic

  • Computer Science

Conference name

16th International Symposium, ISAAC 2005

Conference date

2005-12-19 - 2005-12-21

Conference place

Sanya, Hainan, China

Status

Published

Project

  • VR 2002-4049

ISBN/ISSN/Other

  • ISSN: 1611-3349
  • ISSN: 0302-9743
  • ISBN: 978-3-540-30935-2