Small convex quadrangulations of point sets

被引：0

作者：

Bremner, D ^{[1
]}

Hurtado, F

Ramaswami, S

Sacristán, V

机构：

[1] Univ New Brunswick, Fac Comp Sci, Fredericton, NB E3B 5A3, Canada

[2] Univ Politecn Catalunya, Dept Matemat Aplicada 2, Barcelona, Spain

[3] Rutgers State Univ, Dept Comp Sci, Camden, NJ 08102 USA

来源：

ALGORITHMS AND COMPUTATION, PROCEEDINGS | 2001年 / 2223卷

关键词：

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In this paper, we give upper and lower bounds on the number of Steiner points required to construct a strictly convex quadrilateral mesh for a planar point set. In particular, we show that 3[n/2] internal Steiner points are always sufficient for a convex quadrangulation of n points in the plane. Furthermore, for any given n greater than or equal to 4, there are point sets for which [n-3/2] -1 Steiner points are necessary for a convex quadrangulation.

引用

页码：623 / 635

页数：13

共 22 条

[1] A QUADRILATERAL FINITE-ELEMENT INCLUDING VERTEX ROTATIONS FOR PLANE ELASTICITY ANALYSIS [J].

ALLMAN, DJ .

INTERNATIONAL JOURNAL FOR NUMERICAL METHODS IN ENGINEERING, 1988, 26 (03) :717-730

[2]

ARKIN E, 1994, LECT NOTES COMPUTER, V855, P36

[3]

Benzley S.E., 1995, P 4 INT MESH ROUNDT, VVol. 17, P179

[4] LINEAR-SIZE NONOBTUSE TRIANGULATION OF POLYGONS [J].

BERN, M ;

MITCHELL, S ;

RUPPERT, J .

DISCRETE & COMPUTATIONAL GEOMETRY, 1995, 14 (04) :411-428

[5]

Bern M., 1997, P 6 INT MESH ROUNDT, P7

[6] POLYNOMIAL-SIZE NONOBTUSE TRIANGULATION OF POLYGONS [J].

Bern, Marshall ;

Eppstein, David .

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 1992, 2 (03) :241-255

[7] Characterizing and efficiently computing quadrangulations of planar point sets [J].

Bose, P ;

Toussaint, G .

COMPUTER AIDED GEOMETRIC DESIGN, 1997, 14 (08) :763-785

[8]

BOSE P, 1996, 12 EUR WORKSH COMP G

[9] STATIONING GUARDS IN RECTILINEAR ART GALLERIES [J].

EDELSBRUNNER, H ;

OROURKE, J ;

WELZL, E .

COMPUTER VISION GRAPHICS AND IMAGE PROCESSING, 1984, 27 (02) :167-176

[10]

Eppstein D., 1996, Proceedings of the Twelfth Annual Symposium on Computational Geometry, FCRC '96, P58, DOI 10.1145/237218.237237

← 1 2 3 →