Computing convex quadrangulations

被引：1

作者：

Schiffer, T. ^{[2
]}

Aurenhammer, F. ^{[1
]}

Demuth, M. ^{[1
]}

机构：

[1] Graz Univ Technol, Inst Theoret Comp Sci, A-8010 Graz, Austria

[2] Graz Univ Technol, Inst Comp Graph & Knowledge Visualizat, A-8010 Graz, Austria

来源：

DISCRETE APPLIED MATHEMATICS | 2012年 / 160卷 / 4-5期

关键词：

Irregular quadrilateral mesh; Convex quadrangles; Shape quality; Delaunay tetrahedra; Maximum independent set; QUADRILATERAL MESH GENERATION; SETS; TRIANGULATIONS; SPARSE;

D O I：

10.1016/j.dam.2011.11.002

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We use projected Delaunay tetrahedra and a maximum independent set approach to compute large subsets of convex quadrangulations on a given set of points in the plane. The new method improves over the popular pairing method based on triangulating the point set. (C) 2011 Elsevier B.V. All rights reserved.

引用

页码：648 / 656

页数：9

共 25 条

[1]

AURENHAMMER F, 1991, COMPUT SURV, V23, P345, DOI 10.1145/116873.116880

[2]

Aurenhammer F., 2008, P 5 ANN INT S VOR DI, V4, P32

[3] The Quickhull algorithm for convex hulls [J].

Barber, CB ;

Dobkin, DP ;

Huhdanpaa, H .

ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE, 1996, 22 (04) :469-483

[4] Quadrilateral meshing by circle packing [J].

Bern, M ;

Eppstein, D .

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 2000, 10 (04) :347-360

[5] Experimental results on quadrangulations of sets of fixed points [J].

Bose, P ;

Ramaswami, S ;

Toussaint, G ;

Turki, A .

COMPUTER AIDED GEOMETRIC DESIGN, 2002, 19 (07) :533-552

[6] Small strictly convex quadrilateral meshes of point sets [J].

Bremner, D ;

Hurtado, F ;

Ramaswami, S ;

Sacristán, V .

ALGORITHMICA, 2004, 38 (02) :317-339

[7]

Cormen T., 2001, Introduction to Algorithms

[8]

Edelsbrunner H, 1996, ALGORITHMICA, V15, P223, DOI 10.1007/BF01975867

[9] Dense point sets have sparse delaunay triangulations or "...but not too nasty" [J].

Erickson, J .

DISCRETE & COMPUTATIONAL GEOMETRY, 2005, 33 (01) :83-115

[10]

GABOW HN, 1990, PROCEEDINGS OF THE FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P434

← 1 2 3 →