Approximating the minimum weight triangulation

ABSTRACT

In O(n log n) time we compute a triangulation with O(n) new points, and no obtuse triangles, that has length within a constant factor of the minimum possible. We also approximate the minimum weight Steiner triangulation using triangulations with no sharp angles. No previous polyonomial time triangulation achieved an approximation factor better than O(log n).

REFERENCES

• 1: M. Bern, I4. Edelsbrunner, D. Eppstein, S. Mitchell, and T.S. Tan. Edge-insertion for optimal triangulations. Submitted for conference presentation.
• 2: M. Bern and D. Eppstein. Mesh generation and optimal triangulation, tn Euclidean Geometry and Computers, D.A. Du and F.K. Hwang, eds., World Scientific, to appear.
• 3: Marshall Bern , David Eppstein , John Gilbert, Provably good mesh generation, Journal of Computer and System Sciences, v.48 n.3, p.384-409, June 1994 [doi>10.1016/S0022-0000(05)80059-5]
• 4: Kenneth L. Clarkson, Approximation algorithms for planar traveling salesman tours and minimum-length triangulations, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.17-23, January 28-30, 1991, San Francisco, California, United States
• 5: It. Edelsbrunner and T.S. Tan. A quadratic time algorithm for the minmax length triangulation. Report UIUCDCS-R-91-1665, Univ. Illinois, Urbana- Champaign (1991).
• 6: Herbert Edelsbrunner , Tiow Seng Tan , Roman Waupotitsch, An O(n2log n) time algorithm for the MinMax angle triangulation, Proceedings of the sixth annual symposium on Computational geometry, p.44-52, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98535]
• 7: David Eppstein, The farthest point Delaunay triangulation minimizes angles, Computational Geometry: Theory and Applications, v.1 n.3, p.143-148, March 1992 [doi>10.1016/S0925-7721(98)00031-5]
• 8: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 9: P.D. Gilbert. New results in planar triangulations. Report R-850, Univ. Illinois Coordinated Science Lab (1979).
• 10: D.G. Kirkpatrick. A note on Delaunay and optimal triangulations. Inf. Proc. Lett. 10 (1980) 127-128.
• 11: G.T. Klincsek. Minimal triangulations of polygonal domains. Ann. D~sc. Math. 9 (1980) 121-123.
• 12: Christos Levcopoulos, An &OHgr;(:.PC9 :3WzLn) lower bound for the nonoptimality of the greedy triangulation, Information Processing Letters, v.25 n.4, p.247-251, June 17, 1987 [doi>10.1016/0020-0190(87)90170-0]
• 13: C. Levcopoulos and A. Lingas. On approximation behavior of the greedy triangulation for convex polygons. Algorithmica 2 (1987) 175-193.
• 14: C. Levcopoulos , A. Lingas, Fast algorithms for greedy triangulation, Proceedings of the second Scandinavian workshop on Algorithm theory, p.238-250, July 1990, Bergen, Sweden
• 15: A. Ling~s. Advances in minimum weight triangulation. Ph.D. thesis, LinkSping Univ. (1983).
• 16: E.L. Lloyd. On triangulations of a set of points in the plane. 18th IEEE Symp. Found. Comp. Sci. (1977) 228-240.
• 17: G.K. Manacher and A.L. Zobrist. Neither the greedy nor the Delaunay triangulation approximates the optimum. ln/. Proc. Lett. 9 (1979) 31-34.
• 18: D. M. Mount , A. Saalfeld, Globally-Equiangular triangulations of co-circular points in 0(n log n) time, Proceedings of the fourth annual symposium on Computational geometry, p.143-152, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73408]
• 19: David A. Plaisted , Jiarong Hong, A heuristic triangulation algorithm, Journal of Algorithms, v.8 n.5, p.405-437, Sept. 1987 [doi>10.1016/0196-6774(87)90020-4]
• 20: R. Sibson. Locally equiangular triangulations. Computer J. 21 (1978) 243-245.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

General Terms:
Theory, Verification