On approximation behavior of the greedy triangulation for convex polygons
type: Item
instance of: scholarly article
title: On approximation behavior of the greedy triangulation for convex polygons
zbMATH Open document ID: 0636.68046
DOI: 10.1007/BF01840358
author: Christos Levcopoulos
author: Andrzej Lingas
published in: Algorithmica
publication date: 1987-01-01T00:00:00Z
review text: We prove that the greedy triangulation heuristic for minimum weight triangulation of convex polygons yields solutions within a constant factor of the optimum. - The authors have proved this result independently at the same time. Recently, the result has been generalized by showing that for any polygon P with r reflex angles, the greedy triangulation heuristic yields solutions within an O(r) factor of the optimum. For interesting classes of convex polygons, we derive small upper bounds on the constant approximation factor. Our results contrast with Kirkpatrick's \(\Omega\) (n) bound on the approximation factor of the Delaunay triangulation heuristic for minimum weight triangulation of convex, n-vertex polygons. On the other hand, we present a straightforward implementation of the greedy triangulation heuristic for an n-vertex convex point set or a convex polygon taking \(O(n^ 2)\) time and O(n) space. To derive the latter result, we show that given a convex polygon P, one can find for all vertices v of P a shortest diagonal of P incident to v in linear time. Finally, we observe that the greedy triangulation for convex polygons having so called semi-circular property can be constructed in time O(n log n).
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 52A10
Mathematics Subject Classification ID: 68R99
zbMATH DE Number: 4037199
zbMATH Keywords: time and space complexity
zbMATH Keywords: computational geometry
zbMATH Keywords: greedy triangulation heuristic
zbMATH Keywords: convex polygons
zbMATH Keywords: approximation factor
MaRDI profile type: Publication
cites work: Q5572939
cites work: A note on Delaunay and optimal triangulations
cites work: Minimal Triangulations of Polygonal Domains
cites work: The all nearest-neighbor problem for convex polygons
cites work: Neither the greedy nor the Delaunay triangulation of a planar point set approximates the optimal triangulation
cites work: Q3219752
cites work: Q3992847
cites work: A note on the all nearest-neighbor problem for convex polygons
full work available at URL: https://doi.org/10.1007/bf01840358
OpenAlex ID: W1977014689
Recommended article: Q3003978
Recommended article: Approximation for minimum triangulation of convex polyhedra
Recommended article: A linear-time approximation scheme for minimum weight triangulation of convex polygons
Recommended article: A linear-time approximation scheme for maximum weight triangulation of convex polygons
Recommended article: A greedy algorithm for convex geometries
Recommended article: EFFICIENT APPROXIMATION OF CONVEX POLYGONS
Recommended article: Algorithms for optimal area triangulations of a convex polygon
Recommended article: Greedy drawings of triangulations
Recommended article: Q4474087
description: scientific article; zbMATH DE number 4037199