EDGE INSERTION FOR OPTIMAL TRIANGULATIONS

被引：23

作者：

BERN, M

EDELSBRUNNER, H

EPPSTEIN, D

MITCHELL, S

TAN, TS

机构：

[1] UNIV ILLINOIS, DEPT COMP SCI, URBANA, IL 61801 USA

[2] UNIV CALIF IRVINE, DEPT INFORMAT & COMP SCI, IRVINE, CA 92717 USA

[3] CORNELL UNIV, CTR APPL MATH, ITHACA, NY 14853 USA

[4] NATL UNIV SINGAPORE, DEPT INFORMAT SYST & COMP SCI, SINGAPORE 0511, SINGAPORE

来源：

DISCRETE & COMPUTATIONAL GEOMETRY | 1993年 / 10卷 / 01期

关键词：

D O I：

10.1007/BF02573962

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Edge insertion iteratively improves a triangulation of a finite point set in R2 by adding a new edge, deleting old edges crossing the new edge, and retriangulating the polygonal regions on either side of the new edge. This paper presents an abstract view of the edge insertion paradigm, and then shows that it gives polynomial-time algorithms for several types of optimal triangulations, including minimizing the maximum slope of a piecewise-linear interpolating surface.

引用

页码：47 / 65

页数：19

共 28 条

[1]

[Anonymous], 1987, EATCS MONOGRAPHS THE

[2]

Barnhill RE, 1977, MATH SOFTWARE, V3, P69

[3]

BERN M, 1992, COMPUTING EUCLIDEAN, P23

[4] VORONOI DIAGRAMS FROM CONVEX HULLS [J].

BROWN, KQ .

INFORMATION PROCESSING LETTERS, 1979, 9 (05) :223-228

[5] ON OPTIMAL INTERPOLATION TRIANGLE INCIDENCES [J].

DAZEVEDO, EF ;

SIMPSON, RB .

SIAM JOURNAL ON SCIENTIFIC AND STATISTICAL COMPUTING, 1989, 10 (06) :1063-1075

[6]

Delaunay B., 1934, IZV AKAD NAUK SSSR O, V6, P793

[7] DATA DEPENDENT TRIANGULATIONS FOR PIECEWISE LINEAR INTERPOLATION [J].

DYN, N ;

LEVIN, D ;

RIPPA, S .

IMA JOURNAL OF NUMERICAL ANALYSIS, 1990, 10 (01) :137-154

[8] AN O(N2LOGN) TIME ALGORITHM FOR THE MINMAX ANGLE TRIANGULATION [J].

EDELSBRUNNER, H ;

TAN, TS ;

WAUPOTITSCH, R .

SIAM JOURNAL ON SCIENTIFIC AND STATISTICAL COMPUTING, 1992, 13 (04) :994-1008

[9] SIMULATION OF SIMPLICITY - A TECHNIQUE TO COPE WITH DEGENERATE CASES IN GEOMETRIC ALGORITHMS [J].

EDELSBRUNNER, H ;

MUCKE, EP .

ACM TRANSACTIONS ON GRAPHICS, 1990, 9 (01) :66-104

[10]

EDELSBRUNNER H, 1992, ANIMATION GEOMETRIC, P7

← 1 2 3 →