On approximation behavior of the greedy triangulation for convex polygons
From MaRDI portal
Publication:1098295
DOI10.1007/BF01840358zbMath0636.68046OpenAlexW1977014689MaRDI QIDQ1098295
Andrzej Lingas, Christos Levcopoulos
Publication date: 1987
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01840358
convex polygonscomputational geometryapproximation factortime and space complexitygreedy triangulation heuristic
Analysis of algorithms and problem complexity (68Q25) Convex sets in (2) dimensions (including convex curves) (52A10) Discrete mathematics in relation to computer science (68R99)
Related Items (13)
New results for the minimum weight triangulation problem ⋮ On approximation behavior of the greedy triangulation for convex polygons ⋮ Drawing outerplanar minimum weight triangulations ⋮ A space efficient greedy triangulation algorithm ⋮ Checking the convexity of polytopes and the planarity of subdivisions (extended abstract) ⋮ Fast algorithms for greedy triangulation ⋮ Efficiently updating constrained Delaunay triangulations ⋮ Fast greedy triangulation algorithms. ⋮ Progress on maximum weight triangulation ⋮ Fast algorithms for greedy triangulation ⋮ Heuristics for optimum binary search trees and minimum weight triangulation problems ⋮ Checking the convexity of polytopes and the planarity of subdivisions ⋮ Approximating the minimum weight Steiner triangulation
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On approximation behavior of the greedy triangulation for convex polygons
- A note on Delaunay and optimal triangulations
- The all nearest-neighbor problem for convex polygons
- A note on the all nearest-neighbor problem for convex polygons
- Neither the greedy nor the Delaunay triangulation of a planar point set approximates the optimal triangulation
- Minimal Triangulations of Polygonal Domains
This page was built for publication: On approximation behavior of the greedy triangulation for convex polygons
