NEITHER THE GREEDY NOR THE DELAUNAY TRIANGULATION OF A PLANAR POINT SET APPROXIMATES THE OPTIMAL TRIANGULATION

被引：36

作者：

MANACHER, GK

ZOBRIST, AL

机构：

[1] Department of Information Engineering, Computer Center, University of Illinois

[2] Jet Propulsion Laboratory, Pasadena

来源：

INFORMATION PROCESSING LETTERS | 1979年 / 9卷 / 01期

关键词：

approximately optimal triangulation; Delauney triangulation; Greedy triangulation; Voronoi triangulation;

D O I：

10.1016/0020-0190(79)90104-2

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

[No abstract available]

引用

页码：31 / 34

页数：4

共 8 条

[1]

Christofides, Worst-case analysis of a new heuristic for the Travelling Salesman Problem, Symp. on New Directions and Recent Results in Algorithms and Complexity, (1976)

[2]

Knuth, Big omicron and big omega and big theta, SIGACT news, (1976)

[3]

Lloyd, On triangulations of a set of points in the plane, Proc. 18th Annual IEEE Conference on the Foundations of Computer Science, (1977)

[4]

Manacher, Zobrist, A fast, space-efficient average-case algorithm for the ‘greedy’ triangulation of a point set, and a proof that the greedy triangulation is not approximately optimal, Proc. Sixteenth Annual Allerton Conference on Communication, Control and Computing, (1978)

[5]

Reingold, Nievergelt, Deo, Combinatorial Algorithms, Theory and Practice, (1977)

[6]

Rogers, Packing and Covering, (1964)

[7]

Rosenkrantz, Stearns, Lewis, Approximation algorithms for the Traveling Salesperson Problem, SIAM Journal on Computing, 6, 3, (1977)

[8]

Shamos, Notes on computational geometry, (1975)

← 1 →