A QUADRATIC TIME ALGORITHM FOR THE MINMAX LENGTH TRIANGULATION

被引：22

作者：

EDELSBRUNNER, H ^{[1
]}

TAN, TS ^{[1
]}

机构：

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

来源：

SIAM JOURNAL ON COMPUTING | 1993年 / 22卷 / 03期

关键词：

COMPUTATIONAL GEOMETRY; POINT SETS; TRIANGULATIONS; 2; DIMENSIONS; MINMAX EDGE LENGTH; NORMED METRICS;

D O I：

10.1137/0222036

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

It is shown that a triangulation of a set of n points in the plane that minimizes the maximum edge length can be computed in time 0(n2). The algorithm is reasonably easy to implement and is based on the theorem that there is a triangulation with minmax edge length that contains the relative neighborhood graph of the points as a subgraph. With minor modifications the algorithm works for arbitrary normed metrics.

引用

页码：527 / 551

页数：25

共 27 条

[1] Ajtai M., 1982, ANN DISCRETE MATH, V12, P9
[2] [Anonymous], 1987, EATCS MONOGRAPHS THE
[3] TRIANGULAR ELEMENTS IN FINITE ELEMENT METHOD
BRAMBLE, JH
ZLAMAL, M
[J]. MATHEMATICS OF COMPUTATION, 1970, 24 (112) : 809 - +
[4] Delaunay B., 1934, IZV AKAD NAUK SSSR O, V6, P793
[5] AN O(N2LOGN) TIME ALGORITHM FOR THE MINMAX ANGLE TRIANGULATION
EDELSBRUNNER, H
TAN, TS
WAUPOTITSCH, R
[J]. SIAM JOURNAL ON SCIENTIFIC AND STATISTICAL COMPUTING, 1992, 13 (04): : 994 - 1008
[6] SIMULATION OF SIMPLICITY - A TECHNIQUE TO COPE WITH DEGENERATE CASES IN GEOMETRIC ALGORITHMS
EDELSBRUNNER, H
MUCKE, EP
[J]. ACM TRANSACTIONS ON GRAPHICS, 1990, 9 (01): : 66 - 104
[7] A LINEAR ALGORITHM FOR COMPUTING THE VISIBILITY POLYGON FROM A POINT
ELGINDY, H
AVIS, D
[J]. JOURNAL OF ALGORITHMS, 1981, 2 (02) : 186 - 197
[8] GILBERT PD, 1979, THESIS U ILLINOIS UR
[9] PRIMITIVES FOR THE MANIPULATION OF GENERAL SUBDIVISIONS AND THE COMPUTATION OF VORONOI DIAGRAMS
GUIBAS, L
STOLFI, J
[J]. ACM TRANSACTIONS ON GRAPHICS, 1985, 4 (02): : 74 - 123
[10] JAROMCZYK JW, UNPUB SIAM J COMPUT

← 1 2 3 →