DUALITY OF CONSTRAINED VORONOI DIAGRAMS AND DELAUNAY TRIANGULATIONS

被引：12

作者：

JOE, B

WANG, CA

机构：

[1] Department of Computing Science, University of Alberta, Edmonton, T6G 2H1, Alberta

来源：

ALGORITHMICA | 1993年 / 9卷 / 02期

关键词：

VORONOI DIAGRAM; DELAUNAY TRIANGULATION; DUALITY; COMPUTATIONAL GEOMETRY;

D O I：

10.1007/BF01188709

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We introduce the constrained Voronoi diagram of a planar straight-line graph containing n vertices or sites where the line segments of the graph are regarded as obstacles, and show that an extended version of this diagram is the dual of the constrained Delaunay triangulation. We briefly discuss O(n log n) algorithms for constructing the extended constrained Voronoi diagram.

引用

页码：142 / 155

页数：14

共 11 条

[1]

BONDY JA, 1976, GRAPH THEORY APPLICA

[2]

CHEW LP, 1989, ALGORITHMICA, V4, P97, DOI 10.1007/BF01553881

[3] A SWEEPLINE ALGORITHM FOR VORONOI DIAGRAMS [J].

FORTUNE, S .

ALGORITHMICA, 1987, 2 (02) :153-174

[4]

JOE B, 1988, UNPUB DUALITY CONSTR

[5]

Kirkpatrick D. G., 1979, 20th Annual Symposium of Foundations of Computer Science, P18, DOI 10.1109/SFCS.1979.15

[6] GENERALIZED DELAUNAY TRIANGULATION FOR PLANAR GRAPHS [J].

LEE, DT ;

LIN, AK .

DISCRETE & COMPUTATIONAL GEOMETRY, 1986, 1 (03) :201-217

[7] GENERALIZATION OF VORONOI DIAGRAMS IN THE PLANE [J].

LEE, DT ;

DRYSDALE, RL .

SIAM JOURNAL ON COMPUTING, 1981, 10 (01) :73-87

[8]

Preparata Franco P, 2012, COMPUTATIONAL GEOMET

[9]

SEIDEL R, 1988, IIGTU260 REP, P178

[10]

WANG C, 1987, 3RD P ACM S COMP GEO, P223

← 1 2 →