liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
New results about the approximation behavior of the greedy triangulation
Linköping University, Department of Computer and Information Science. Linköping University, The Institute of Technology.
1986 (English)Licentiate thesis, monograph (Other academic)
Abstract [en]

In this paper it is shown that there is some constant c, such that for any polygon, with or without holes, with w concave vertices, the length of any greedy triangulation of the polygon is not longer than c x (w + 1) times the length of a minimum weight triangulation of the polygon (under the assumption that no three vertices lie on the same line). A low approximation constant is proved for interesting classes of polygons. On the other hand, it is shown that for every integer n greater than 3, there exists some set S of n points in the plane, such that the greedy triangulation of S is W(n1/2) times longer than the minimum weight triangulation (this improves the previously known W(n1/3) lower bound). Finally, a simple linear-time algorithm is presented and analyzed for computing greedy triangulations of polygons with the so called semi-circle property.

Place, publisher, year, edition, pages
Linköping: Department of Computer Science, Linköpings universitet , 1986. , p. 25
Series
Linköping Studies in Science and Technology. Thesis, ISSN 0280-7971 ; 74
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:liu:diva-156611ISBN: 9178700698 (print)OAI: oai:DiVA.org:liu-156611DiVA, id: diva2:1307638
Available from: 2019-04-29 Created: 2019-04-29 Last updated: 2019-04-29Bibliographically approved

Open Access in DiVA

No full text in DiVA

By organisation
Department of Computer and Information ScienceThe Institute of Technology
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 2 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf