Strategies for polyhedral surface decomposition: An experimental study

被引：68

作者：

Chazelle, B

Dobkin, DP

Shouraboura, N

Tal, A

机构：

[1] PRINCETON UNIV,DEPT COMP SCI,PRINCETON,NJ 08544

[2] PRINCETON UNIV,PROGRAM APPL & COMPUTAT MATH,PRINCETON,NJ 08544

[3] WEIZMANN INST SCI,DEPT COMP SCI,IL-76100 REHOVOT,ISRAEL

来源：

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | 1997年 / 7卷 / 5-6期

基金：

美国国家科学基金会;

关键词：

NP-completeness; 3-SAT; convexity; surface decomposition; flooding heuristics;

D O I：

10.1016/S0925-7721(96)00024-7

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

This paper addresses the problem of decomposing a complex polyhedral surface into a small number of ''convex'' patches (i.e., boundary parts of convex polyhedra). The corresponding optimization problem is shown to be NP-complete and an experimental search for good heuristics is undertaken. (C) 1997 Elsevier Science B.V.

引用

页码：327 / 342

页数：16

共 21 条

[1] Amenta N., 1995, Proceedings of the Eleventh Annual Symposium on Computational Geometry, pC12
[2] [Anonymous], P 9 ANN S COMP GEOM
[3] [Anonymous], 1987, ART GALLERY THEOREMS
[4] CASTLES IN THE AIR REVISITED
ARONOV, B
SHARIR, M
[J]. DISCRETE & COMPUTATIONAL GEOMETRY, 1994, 12 (02) : 119 - 150
[5] TRIANGLES IN SPACE OR BUILDING (AND ANALYZING) CASTLES IN THE AIR
ARONOV, B
SHARIR, M
[J]. COMBINATORICA, 1990, 10 (02) : 137 - 173
[6] CONVEX DECOMPOSITION OF POLYHEDRA AND ROBUSTNESS
BAJAJ, CL
DEY, TK
[J]. SIAM JOURNAL ON COMPUTING, 1992, 21 (02) : 339 - 364
[7] BERN M, 1992, WORLD SCI SERIES COM, P23
[8] BERN M, 1990, 31 ANN S FDN COMP SC, P231
[9] CONVEX PARTITIONS OF POLYHEDRA - A LOWER BOUND AND WORST-CASE OPTIMAL ALGORITHM
CHAZELLE, B
[J]. SIAM JOURNAL ON COMPUTING, 1984, 13 (03) : 488 - 507
[10] TRIANGULATING A NONCONVEX POLYTOPE
CHAZELLE, B
PALIOS, L
[J]. DISCRETE & COMPUTATIONAL GEOMETRY, 1990, 5 (05) : 505 - 526

← 1 2 3 →